merge sort - cocoder39/coco39_LC GitHub Wiki

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

using namespace std;

void merge (vector<int>& nums, vector<int>& aux, int low, int mid, int high) {
    for (int i = low; i <= high; i++) { //copy
        aux[i] = nums[i];
    }
  
    int i = low;
    int j = mid + 1;
    for (int k = low; k <= high; k++) {
        if (i > mid) { // lower side is empty
            nums[k] = aux[j++];
        } else if (j > high) {
            nums[k] = aux[i++]; // higher side is empty
        } else if (aux[i] <= aux[j]) {
            nums[k] = aux[i++];
        } else {
            nums[k] = aux[j++];
        }
    }
}

void sortHelper (vector<int>& nums, vector<int>& aux, int low, int high) {
    if (high <= low) {
        return;
    }
    
    int mid = low + (high - low) / 2;
    sortHelper(nums, aux, low, mid);
    sortHelper(nums, aux, mid + 1, high);
    if (nums[mid] <= nums[mid + 1]) { //already sorted
        return;
    }
    merge(nums, aux, low, mid, high);
}

void mergeSort(vector<int>& nums) {
    int sz = nums.size();
    if(sz == 0) {
        return;
    }
    vector<int> aux(sz);
    sortHelper(nums, aux, 0, sz - 1);
}

void insertSort (vector<int>& nums) {
    if (nums.size() <= 1) {
        return;
    }
    
    for (int i = 1; i < nums.size(); i++) {
        for (int j = i; j >= 1; j--) {
            if (nums[j] < nums[j - 1]) {
                swap(nums[j - 1], nums[j]);
            }
        }
    }
}
  
int main() {
    vector<int> nums{7, 8, 30, 4, 5, 8, 19};
    if (nums.size() <= 10) {
        insertSort(nums);
    } else {
        mergeSort(nums);
    }  
  
    for (auto num : nums) {
        cout << num << "\t" << endl;
    }
    return 0;
}