二路归并排序

归并排序可以看作一个分而治之的过程：先将整个序列分成两半，对每一半分别进行归并排序，将得到两个有序序列，然后将这两个序列归并成一个序列即可。

二路归并排序图解.png

代码：

#include <iostream>
#include <limits.h>
using namespace std;

void merge(int array[], int low, int mid, int high) {
  int *temp = new int[high - low + 1];
  int i, j, k;
  i = low;
  j = mid + 1;
  k = 0;
  while (i <= mid && j <= high) {
    if (array[i] <= array[j])
      temp[k++] = array[i++];
    else 
      temp[k++] = array[j++];
  }

  while (i <= mid) {
    temp[k++] = array[i++];
  }

  while (j <= high) {
    temp[k++] = array[j++];
  }

  for (k = 0; k < high - low + 1; ++k) {
    array[low + k] = temp[k];
  }
}

void MergeSort(int array[], int low, int high) {
  if (low < high) {
    int mid = (low + high) / 2;
    MergeSort(array, low, mid);
    MergeSort(array, mid + 1, high);
    //把array数组中的low到mid和mid+1到high范围内的
    //两段有序序列归并成一段有序序列.
    merge(array, low, mid, high);
  }
}

void print_array(int array[], int n) {
  for (int i = 0; i < n; ++i)
    cout<<array[i]<<" ";
  cout<<endl;
}

int main() {
  int array[] = {4, 3, 1, 7, 2, 9, 12};
  print_array(array, 7);
  MergeSort(array, 0, 6);
  print_array(array, 7);

  return 0;
}

复杂度分析：

1.时间复杂度：
归并排序中可选merge( )中的“归并操作”作为基本操作。函数merge( )的“归并操作”执行次数为要归并的两个子序列中关键字的个数之和。
第一趟归并需要执行 2×(n/1)=n次基本操作（其中，2为两子序列关键字个数之和，n/2为要归并的子序列对的个数；每个子序列对执行执行一次函数merge( ),也就是两次基本操作）
第二趟归并需要执行4×(n/4)=n次基本操作。
第三趟归并需要执行8×(n/8)=n次基本操作。
...
第k趟归并需要执行2^k * (n/2^k)=n次基本操作。
...
当n/2^k=1时，即需要归并的两个子序列长度均为原序列的一半，只需要执行一次函数merge( )归并排序即可结束，此时k=log2^n。
即总共需要进行log2^n趟排序，每趟排序执行n次基本操作。
因此整个归并排序中总的基本操作执行次数为nlog2^n。
时间复杂度为O(nlog2^n)，且与初始序列无关。

2.空间复杂度：
从merge( )中可看出，需要转存整个待排序列，因此空间复杂度为O(n).