《数据结构与算法——C语言实现》学习笔记——归并排序_sduzh的专栏

/**************************************************
* Copyright(C):
* Filename:merge_sort.cpp
* Author: 
* Version:
* Data:   18 sep 2013 
* Description:
***************************************************/

#include "merge_sort.h"


//--------------------------------------------
// Merge()
//
//
//
void 
Merge(Type *A, int p, int q, int r){
    int i,j,k;
    int n1,n2;

    n1 = q-p;
    n2 = r-q+1;


    Type *L = new Type[ n1+1 ];
    Type *R = new Type[ n2+1 ];

    for ( i=0; i<n1; i++ ){
        L[ i ] = A[ p+i ];
    }
    L[ i ] = INIFITE;
    
    for ( j=0; j<n2; j++ ){
        R[ j ] = A[ q+j ];
    }
    R[ j ] = INIFITE;

    i = 0;
    j = 0;
    for ( k=p; k<=r; k++ ){
        if ( L[ i ] < R[ j ] ){
            A[ k ] = L[ i++ ];
        }
        else{
            A[ k ] = R[ j++ ];
        }    
    }

    delete [] L;
    delete [] R;
}


//------------------------------------------
// MergeSort()
//
//
//
void 
MergeSort(Type *A, int p, int r){
    int q;
    if ( p < r ){
        q = (p+r)/2;
        MergeSort(A, p, q);
        MergeSort(A, q+1,r);
        merge(A,p,q+1,r);
    }
}
/**********************************************