归并排序

没想到面试的时候还是被问到了，当时连归并的大致流程都说不出来，实在是觉得很尴尬，今天重新学一下，附上理解并实现的代码。

归并排序的思想就是分而治之，递归地把一个序列一分为二，每次将上一步得到的有序子序列合并到一起。

演示过程：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
const int maxn = 2e6 + 10;
int a[maxn], n;
typedef long long ll;

void merge(int a[], int low, int mid, int high) {
  // 假设现在有两个排好序的子数组subarr1 = a[low...mid], subarr2 = a[mid + 1...high],  
  int N = high - low + 1;
  int b[N]; 
  int left = low, right = mid + 1, idx = 0;
  while (left <= mid && right <= high)
    b[idx++] = a[left] < a[right] ? a[left++] : a[right++]; // 归并，把小的放在前面 
  while (left <= mid) b[idx++] = a[left++]; //有剩余的直接放在末尾，下一行同理 
  while (right <= high) b[idx++] = a[right++];
  for (int i = 0; i < N; i++) a[low + i] = b[i];//拷贝回原数组 
}

void mergeSort(int a[], int low, int high) {
  if (low < high) {
    int mid = (low + high) / 2;
    mergeSort(a, low, mid);
    mergeSort(a, mid + 1, high);
    merge(a, low, mid, high);
  }
}
void print() {
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  cout << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  srand(time(0));
  for (int i = 0; i < n; i++) {
    a[i] = rand() % maxn;
  }
  print();
  mergeSort(a, 0, n - 1);
  print();
  return 0;
}