C＋＋编程：C++归并排序实现（算法导论）

　　算法导论上的下标是从1开始的，但是为了和c++ STL的设计思想一致，所有函数的实现统一用左闭右开区间。中间修改了很多次，因为下标修改不是很容易就改掉的，需要始终维持循环不变式，稍微一个步骤出错就会使结果有些错误。

　　#include

　　#include

　　#include

　　#include

　　using namespace std;

　　void merge(int *A, int p, int q, int r) { //merge [p, r)，左闭右开区间

　　int n1 = q - p, n2 = r - q; //注意数量的变化与书上的不同，使用左闭右开区间的优势就是统一数量的形式表示

　　int *L = new int[n1], *R = new int[n2];

　　for (int i = 0; i < n1; ++i) //L[0, n1) <== A[p, q)

　　L[i] = A[p+i];

　　for (int i = 0; i < n2; ++i) //R[0, n2) <== A[q, r)

　　R[i] = A[q+i]; //此处不是q+i+1

　　int i = 0, j = 0;

　　int k = p;

　　while (i < n1 && j < n2) {

　　if (L[i] <= R[j])

　　A[k++] = L[i++];

　　else

　　A[k++] = R[j++];

　　}

　　while (i < n1) //由于没有了哨兵，需要添加多余元素

　　A[k++] = L[i++];

　　while (j < n2)

　　A[k++] = R[j++];

　　delete [] L;

　　delete [] R;

　　}

　　void merge_sort(int *a, int p, int r) { //调用接口 merge_sort(a, 0, len)， 不是(a, 0, len-1)了

　　if (p < r - 1) { //此时不是p < r了，左闭右开区间当p>=r-1时子数组最多一个元素

　　int q = p + (r - p)/2;

　　merge_sort(a, p, q);

　　merge_sort(a, q, r); //注意接口统一了，这个不是(a, q+1, r)而是(a, q, r)了，左闭右开的好处

　　merge(a, p, q, r);

　　}

　　}

　　int main()

　　{

　　srand(time(NULL));

　　int n;

　　while (cin 》 n) {

　　int a[n];

　　for (int i = 0; i < n; ++i)

　　a[i] = rand() % n;

　　for (int i = 0; i < n; ++i)

　　printf("%d ", a[i]);

　　printf("n");

　　merge_sort(a, 0, n);

　　for (int i = 0; i < n; ++i)

　　printf("%d ", a[i]);

　　printf("n");

　　}

　　}

　　最后用了几万组测试数据，得出的结果均与stl里的sort结果一样， 基本说明这个代码是正确的。