#include <stdio.h>#include <stdlib.h>void Merge(int A[] , int TmpArray[] , int Lpos , int Rpos , int RightEnd);void MSort(int A[] , int TmpArray[] , int Left , int Right);void MergeSort(int A[] , int N);int main(int argc, const char * argv[]) {        int A[15] = { 9,8,6,7,5,3,4,1,2,0,4,7,8,3,2};        MergeSort(A, 15);        int B[12] = { 1 , 3, 4, 5, 9 ,2, 5,6,7,8,10,11} ;        int *Tmp = malloc(sizeof(int) * 12);        //Merge(B, Tmp, 0, 5, 11);    MSort(B, Tmp, 0, 12);    //Merge(B, Tmp, 0, 7, 12);            for (int i = 0 ; i < 12 ; i++)        printf("%d " , B[i]);    return 0;}// merge 过程，其主要的作用是合并两个已经排序的数组// 由于这里是一个数组，我们要合并数组的前半部分和后半部分// Lpos 是前半部分是的开头，Rpos是后半部分的开头// RightEnd 是右半部分的结尾。// 同时，我们需要一个临时数组来存储TmpArray，事后将临时数组// 拷贝回来，void Merge(int A[] , int TmpArray[] , int Lpos , int Rpos, int RightEnd){    int i , LeftEnd , NumElements , TmpPos;        LeftEnd = Rpos - 1 ; //数组的左半部分最后一个元素位置    TmpPos = Lpos; //临时数组的开始位置    NumElements = RightEnd - Lpos + 1 ; //元素的总个数        /* main loop */    while ( Lpos <= LeftEnd && Rpos <= RightEnd)        if (A[Lpos] <= A[Rpos])            TmpArray[TmpPos ++] = A[Lpos ++];        else            TmpArray[TmpPos ++] = A[Rpos ++];        while (Lpos <= LeftEnd)        TmpArray[TmpPos ++] = A[Lpos ++];    while (Rpos <= RightEnd)        TmpArray[TmpPos ++] = A[Rpos ++];        for ( i = 0 ; i < NumElements ; i++ , RightEnd --)        A[RightEnd] = TmpArray[RightEnd]; // 注意这里，我当时写的是A[i] ,注意其                                         // 表达的意思，递归在某一段使用merge操作        }//Msort 的递归调用，其时间复杂度很好分析void MSort(int A[] , int TmpArray[] , int Left , int Right){    int Center ;        if (Left < Right) {  //注意这里我写的是Left < Center，调试了非常久才找出来！        Center = (Left + Right) / 2 ;        MSort(A, TmpArray, Left, Center);        MSort(A, TmpArray, Center + 1, Right);        Merge(A, TmpArray, Left, Center + 1 , Right);    }        }//递归调用的驱动程序void MergeSort(int A[] , int N){    int *TmpArray;        TmpArray = malloc( N * sizeof(int));    if (TmpArray != NULL) {        MSort(A, TmpArray, 0, N - 1 );        free(TmpArray);    }    else    {        printf("Out of space!!");    }}