归并排序

• 全称 Merge sort

• 特点

  • 稳定
  • 时间复杂度
    • 最优、平均、最坏均为 O(nlogN)
  • 空间复杂度
    • O(n) , 因为需要牺牲额外的空间temp来实现，这是它的缺点

• 原理

  • 分成两段，调用递归分别排序，这样返回后这两段就是分别有序的
  • 然后把这两个有序段A和B合并就行，中途需要借助一个temp数组
    • 合并方法: 从B中依次摘取，如果它比A的最小的还要小，就优先放到temp中，一旦不满足比A中最小的小，那就把A中最小的放到temp中

let mergeSort = (arr, temp, ll, rr) => {
    if (rr - ll <= 1) return;
    const mid = ll + ((rr - ll) >> 1);
    mergeSort(arr, temp, ll, mid);
    mergeSort(arr, temp, mid, rr);
    
    let p = ll, q = mid, s = ll;
    while (s < rr) {
      if (p >= mid || (q < rr && arr[q] < arr[p])) {
          temp[s++] = arr[q++];
      } else {
          temp[s++] = arr[p++];
      }
    }

    for (let i = ll; i < rr; ++i) arr[i] = temp[i];
};

let shuffle = (arr) => {
    let n = arr.length;
    while (n > 0) {
        const random = (Math.random() * n--) >>> 0;
        [arr[random], arr[n]] = [arr[n], arr[random]];
    }
    return arr;
}

(() => {
    let testArr = [5, 7, 3, 4, 2, 6, 1];
    shuffle(testArr);
    const temp = new Array(testArr.length).fill(0);
    mergeSort(testArr, temp, 0, testArr.length);
    console.log(testArr);
})()

#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;

void mergeSort(vector<int>& arr, vector<int>& temp, int ll, int rr){
    if (rr - ll <= 1) return;
    int mid = ll + ((rr - ll) >> 1);
    mergeSort(arr, temp, ll, mid);
    mergeSort(arr, temp, mid, rr);
    
    int p = ll, q = mid, s = ll;
    while (s < rr) {
      if (p >= mid || (q < rr && arr[q] < arr[p])) {
          temp[s++] = arr[q++];
      } else {
          temp[s++] = arr[p++];
      }
    }

    for (int i = ll; i < rr; ++i) arr[i] = temp[i];
};

void shuffle(vector<int>& arr) {
    int n = arr.size();
    srand(time(NULL));
    while (n--) {
        const int random = rand() % arr.size();
        swap(arr[n], arr[random]);
    }
}

int main() {
    vector<int> testArr = {5, 7, 3, 4, 2, 6, 1};
    shuffle(testArr);
    vector<int> temp(testArr.size(), 0);
    mergeSort(testArr, temp, 0, testArr.size());
    for(auto e: testArr) cout<<e<<endl;
    return 0;
}