归并排序（Merge）

有序序列两两合并

稳定

空间复杂度O（n）,时间复杂度O(nlogn)

int* B = (int*)malloc(sizeof(int) * n);

void sort(int num[], int low, int high) {

if (low < high) {

int mid = (low + high) / 2;

sort(num, low, mid);

sort(num, mid+1, high);

Merge(num, low, mid, high);

}

}

void Merge(int num[],int low,int mid,int high) {

int i, j, k;

for (k = low; low <= high; k++) {//复制

B[k] = num[k];

}

//i,j,k分别指向三个数组的元素

for (i = low, j = mid + 1,k=low; i < mid && j < high; k++) {

if (B[i] > B[j]) num[k] = B[j++];//

else num[k] = B[i++];//

}

while (i <= mid) num[k++] = B[i++];

while(j<=high) num[k++] = B[j++]

}