Merge sorting algorithm implemented by C++.

merge_sort.cpp

/*
 * @author  duruyao
 * @file    merge_sort.cpp
 * @desc    
 * @date    2021-10-02
 * @version 1.0
 */

#include <vector>
#include <iostream>

/**
 * mergeSort sorts data set by merge sorting algorithm.
 *
 * ---time complexity---
 *
 * best    case:    O(n * log n)
 * average case:    O(n * log n)
 * worst   case:    O(n * log n)
 *
 * ---space complexity---
 *
 * always: O(n)
 *
 * ---when to use---
 *
 * (1) algorithm is required to sort stably (keep the relative order of equal elements unchanged after sorting) AND
 * (2) extra storage space is allowed.
 *
 * ---parameters and return---
 *
 * @tparam T        is a certain data type
 * @param input     is a data set to be sorted
 * @param output    is a data set contains sorting result
 * @param begin     is the first index
 * @param end       is the index past the last index
 * @param cmpFunc   is a function for comparing elements of data set
 */
template<typename T>
void mergeSort(std::vector<T> &input, std::vector<T> &output,
               int begin, int end, int (*cmpFunc)(const T &, const T &)) {
    if (end - begin <= 1) {
        return;
    } else if (end - begin == 2) {
        if (cmpFunc(input[begin], input[begin + 1]) > 0) {
            std::swap(output[begin], output[begin + 1]);
        }
        return;
    }
    auto mid = (begin + end - 1) / 2;
    mergeSort(output, input, begin, mid, cmpFunc);
    mergeSort(output, input, mid, end, cmpFunc);
    for (int i = begin, j = mid, k = begin; k < end; k++) {
        if (i >= mid) {
            output[k] = input[j++];
        } else if (j >= end) {
            output[k] = input[i++];
        } else {
            output[k] = (input[i] <= input[j]) ? input[i++] : input[j++];
        }
    }
}

int cmpInt(const int &n1, const int &n2) {
    return n1 - n2;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &input) {
    for (auto &it : input) { os << it << " "; }
    return os;
}

int main(int argc, char **argv) {
    std::vector<int> array;
    for (int i = 0; i < 40; array.push_back(random() % 100), i++);
    std::vector<int> backup(array);
    std::cout << array << std::endl;
    mergeSort(backup, array, 0, (int) array.size(), cmpInt);
    std::cout << array << std::endl;
    return 0;
}