How one can perfome merge sort in C++ using STL?

Question

explained with code will be helpful.

Answer 1

Merge Sort

Merge sort is a divide-and-conquer algorithm, the idea is first splitting data into two subsets, then sort then merge. The time complexity is O(nlogn)O(nlog⁡n) with O(n)O(n) extra memory.

It is not difficult to implement a recursive version merge sort in C++ or Java, or Python, etc. However, using STL, it takes no more than 10 lines of code to implement a merge sort algorithm [1].

The key is using function std::inplace_merge [1]: the function comes with two signatures:.

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

template< class BidirIt, class Compare>
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );

The function merges two consecutive sorted ranges [first, middle) and [middle, last) into a sorted range [first, last). The default comparison operation is less than.

Following example is from [1]:

#include <vector>
#include <iostream>
#include <algorithm>

template<class Iter>
void merge_sort(Iter first, Iter last){
    if (last - first > 1) {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle); // [first, middle)
        merge_sort(middle, last);  // [middle, last)
        std::inplace_merge(first, middle, last);
    }
}

int main(){
    std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for(auto n : v) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

Note that

the parameters of bidirectional iterator type should meet requirements of ValueSwappable (can be parsed by std::swap()).

the dereferenced type of bidirectional iterator should meet the requirements of MoveAssignable and MoveConstructible. In other words, the dereferenced type should at least support a copy assignment operation and have a copy constructor.