Merge Sort (合併排序法) ＊＊＊

概念 - 教學影片

學完遞回, Divide and Conquer 後再回來看

作法

Pseudo Code

const int N = 10;
int students[N] = {4,3,5,1,7,18,12,3,2,2};
int buffer[N];


void Sort( int left, int mid, int right ){

    int lptr = left, rptr = mid+1;
    int ptr = 0;

    while ( lptr <= mid && rptr <= right ){
        if ( students[lptr] < students[rptr] )
            buffer[ptr++] = students[lptr++];        
        else
            buffer[ptr++] = students[rptr++];
    }

    while ( lptr <= mid )
        buffer[ptr++] = students[lptr++];      
    while ( rptr <= right )
        buffer[ptr++] = students[rptr++];

    for ( int i = 0, j = left ; j <= right ; i++, j++ )
        students[j] = buffer[i];



}

void Merge( int left, int right ){

    if ( left >= right ) return;

    int mid = ( left + right ) / 2;

    Merge( left, mid );
    Merge( mid+1, right );

    Sort( left , mid , right );
}



Merge( 0, N-1 );