merge_sort.hpp

• View this file on GitHub
• Last update: 2024-06-03 04:10:09+09:00
• Include: #include "merge_sort.hpp"

Code

template <class Iterator, class Compare>
void merge_sort(Iterator first, Iterator last, Compare comp) {
    const auto d = last - first;
    if (d <= 1) return;
    if (d == 2) {
        if (!comp(*first, *(first + 1))) swap(*first, *(first + 1));
        return;
    }
    merge_sort(first, first + d / 2, comp);
    merge_sort(first + d / 2, last, comp);
    inplace_merge(first, first + d / 2, last, comp);
}

#line 1 "merge_sort.hpp"
template <class Iterator, class Compare>
void merge_sort(Iterator first, Iterator last, Compare comp) {
    const auto d = last - first;
    if (d <= 1) return;
    if (d == 2) {
        if (!comp(*first, *(first + 1))) swap(*first, *(first + 1));
        return;
    }
    merge_sort(first, first + d / 2, comp);
    merge_sort(first + d / 2, last, comp);
    inplace_merge(first, first + d / 2, last, comp);
}

Back to top page