Merge sort

Merge sort [1] combining two ordered arrays to make one larger ordered array. This recursive method sorts an array, divide it into two halves, sort the two halves (recursively), and then merge the results. Merge sort guarantees to sort an array of N items in time proportional to N log N, no matter what the input. Its prime disadvantage is that it uses extra space proportional to N.

For implementation we use the next rules: Sequence with 0 or 1 element is always ordered.

Half the input sequence
    Recursive order the two part
    Merge the ordered subparts

title

The merge method merges two ordered sequence to a result array.

/// Merge two ordered sequences
    template<typename Iter>
    void mergeRanges(Iter it1, Iter end1, Iter it2, Iter end2, Iter it3) {
        while (it1 != end1 && it2 != end2) {
            if (*it1 < *it2)
                *(it3++) = *(it1++);
            else if (*it1 > *it2)
                *(it3++) = *(it2++);
            else {
                *(it3++) = *(it1++);
                *(it3++) = *(it2++);
            }
        }
        while (it1 != end1)
            *(it3++) = *(it1++);
        while (it2 != end2)
            *(it3++) = *(it2++);
    }

The mergeSort method halves the sequence, calculates the new borders and call itself in a recursive way. If the recursion stops, mergeRanges method performs and its result is an ordered sequence. mergeSort method without “” is only a wrapper to bind the details from the user.

template<typename Iter>
    void _mergeSort(Iter first, Iter last, Iter buffer, Iter buffer_end) {
        if (std::distance(first, last) > 1) {
            auto middle = first + std::distance(first, last) / 2;
            auto buffer_middle = buffer + std::distance(first, last) / 2;
            _mergeSort(first, middle, buffer, buffer_middle);
            _mergeSort(middle, last, buffer_middle, buffer_end);
            mergeRanges(first, middle, middle, last, buffer);
            std::copy(buffer, buffer_end, first);
        }
    }
    
    template<typename Iter>
    void mergeSort(Iter first, Iter last) {
        typedef typename std::iterator_traits<Iter>::value_type ValueType;
        ValueType* buffer = new ValueType[std::distance(first, last)];
        _mergeSort(first, last, buffer, buffer + std::distance(first, last));
    
        delete[] buffer;
    }

With main function we can test our merge sort method.

#include <iostream>
    #include <random>
    #include <functional>
    #include <ctime>
    
    const int n = 10;
    
    ////////// Using random generator engine //////////
    std::default_random_engine gen((unsigned int)std::time(0));
    std::uniform_int_distribution<int> distribution(1, 50);
    auto randInt = std::bind(distribution, gen); // using randInt() generate integer number between (1-50)
    
    template<class Iter>
    void printArray(Iter begin, Iter end) {
        for (auto i = begin; i != end; i++) {
            std::cout << *i << ", ";
        }
        std::cout << std::endl;
    }
    
    template<class Iter>
    void testSorting(int* testArray, void(*sort)(Iter, Iter)) {
        std::cout << "original:  ";
        printArray(testArray, testArray + n);
    
        sort(testArray, testArray + n);
        std::cout << "sorted:  ";
        printArray(testArray, testArray + n);
    }

std::cout << "Testing sort algorithms ...\n\n";
    
    int* test = new int[n];
    
    auto generate = [](decltype(test[0]) i){ i = randInt(); };
    std::for_each (test, test + n, generate);
    
    std::cout << "*** Merge sort: ***\n";
    testSorting<decltype(test)> (test, mergeSort);
    std::cout << "\n";
    
    delete[] test;