算法导论上的下标是从1开始的，但是为了和c++ STL的设计思想一致，所有函数的实现统一用左闭右开区间。中间修改了很多次，因为下标修改不是很容易就改掉的，需要始终维持循环不变式，稍微一个步骤出错就会使结果有些错误。
#include <IOSTREAM>
#include <CSTDIO>
#include <CSTDLIB>
#include <CTIME>
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结果一样， 基本说明这个代码是正确的。