#include"iostream"

using namespace std;

//让两个数组融合

int Merge(int a[], int low,int mid,int high){

//space暂时的数组去存储融合好的两个数组！

int *space = (int *)malloc(sizeof(int)*(high - low + 1));

if (space == NULL){

return -1;

}

int l = low;

int m = mid+1;

int h = high; 

int i = 0;

//红色部分是将两个数组融合的关键

while ((l<= mid)&&(m <= high)){

space[i++] = (a[l]>a[m]) ? a[m++] : a[l++];

//注意这里你取走谁的值就实行自加；

}

while (l <=mid){//第一个数组有剩余！

space[i++] = a[l++];

}

while (m <= high){//第二个数组有剩余！

space[i++] = a[m++];

}

for (int i = low,k=0; i <=high; i++,k++){

a[i] = space[k];//让临时数组的值全都赋值过去

}

return 0;

}

void MergeSort(int a[], int low, int high){

if (low < high){

int mid=(low+high)/2;

//采用分冶法进行排序。让数组中一部分一部分的排好。最后慢慢融合

MergeSort(a, low, mid);//让a[low]到a[mid]排好序！

MergeSort(a, mid + 1, high);//让a[mid+1]到a[high]排好序！

Merge(a, low, mid, high);//最后融合

}

return;

}

int main()

{

//int array[] = {21, 25, 49, 25, 16, 8};

int array[] = { 21, 25,56,32,14,5,7,8,64 };

int len = sizeof(array) / sizeof(*array);

MergeSort(array, 0,len-1);

for (int i = 0; i < len; i++){

cout << array[i] << " ";

}

cout << endl;

system("pause");

return 0;

}

归并排序