递归法（有序子列的归并）

/*    有序子列的归并  */
// T = O( N )
/*  L = 左边起始位置，R = 右边起始位置， RightEnd = 右边终点位置  */
void Merge ( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd ) {
    LeftEnd = R - 1;  /* 左边终点位置。假设左右两列挨着   */
    Tmp = L;   /*  存放结果的数组的起始位置  */ 
    NumElements = RightEnd - L + 1;
    
    while ( L <= LeftEnd && R <= RightEnd ) {
        if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
        else                TmpA[Tmp++] = A[R++];
    }
    while ( L <= LeftEnd )  //  直接复制左边剩下的
        TmpA[Tmp++] = A[L++];
    while ( R <= RightEnd )  // 直接复制右边剩下的
        TmpA[Tmp++] = A[R++];
    for ( i=0; i<NumElements; i++, RightEnd-- )
        A[RightEnd] = TmpA[RightEnd];  //  导出
}


/*  递归算法  分而治之  */
//  T = O( NlogN )
void MSort ( ElementType A[], ElementType TmpA[], int L, int RightEnd ) {
    int Center;
    
    if ( L < RightEnd ) {
        
        Center = ( L + RightEnd ) / 2;
        
        MSort ( A, TmpA, L, Center );   //  递归处理左半边
        MSort ( A, TmpA, Center+1, RightEnd );   //递归处理右半边
        
        Merge ( A, TmpA, Center+1, RightEnd );   //  归并
    }
}

/*  统一函数接口   递归排序  */
void Merge_sort ( ElementType A[], int N ) {
    ElementType *TmpA;
    TmpA = malloc(sizeof( ElementType ));
    if ( TmpA != NULL ) {
        MSort ( A, TmpA, 0, N-1 );
        free ( TmpA );
    }
    else  Error ( "空间不足" );
}

非递归法

/*    有序子列的归并  */
// T = O( N )
/*  L = 左边起始位置，R = 右边起始位置， RightEnd = 右边终点位置  */
void Merge ( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd ) {
    
    LeftEnd = R - 1;  /* 左边终点位置。假设左右两列挨着   */
    Tmp = L;   /*  存放结果的数组的起始位置  */ 
    NumElements = RightEnd - L + 1;
    
    while ( L <= LeftEnd && R <= RightEnd ) {
        if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
        else                TmpA[Tmp++] = A[R++];
    }
    
    while ( L <= LeftEnd )  //  直接复制左边剩下的
        TmpA[Tmp++] = A[L++];
    
    while ( R <= RightEnd )  // 直接复制右边剩下的
        TmpA[Tmp++] = A[R++];
    
    for ( i=0; i<NumElements; i++, RightEnd-- )
        A[RightEnd] = TmpA[RightEnd];  //  导出
}

void Merge_pass ( ElementType A[], ElementType TmpA[], int N, int length ) {  // length 为当前有序子列长度
    
    for ( i=0; i <= N-2*length; i += 2*length )
        Merge ( A, TmpA, i, i+length, i+2*length-1 );
    
    if ( i+length < N )             //  归并最后两个子列
        Merge ( A, TmpA, i, i+length, N-1 );
    
    else      //  最后只剩一个子列
        for ( j=i; j < N; j++ ) TmpA[j] = A[j];
}

/*  稳定排序   */
void Merge_sort ( ElementType A[], int N ) {
    
    int length = 1;   //  初始化子列长度
    ElementType *TmpA;
    TmpA = malloc( N*sizeof ( ElementType ));
    
    if ( TmpA != NULL ) {
        
        while ( length < N ) {
            
            Merge_pass ( A, TmpA, N, length );
            length *= 2;
            Merge_pass ( TmpA, A, N, length  );
            length *= 2;
        }
        free ( TmpA );
    }
    
    else Error ( "空间不足" );
}