合併排序

合併就是把兩堆已經排序好的資料

按大小重新排列成一堆

//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
#define  LEFT      'L'
#define  RIGHT     'R'
//---------------------------------------------------------------------------
int      g_icount = 1;
//---------------------------------------------------------------------------
void mergeSort(int *list, int *tmp, char type, int left, int right)
{
    if(left >= right) return;
   
    int middle = (left+right)/2;
   
    mergeSort(list, tmp, LEFT,  left,     middle);
    mergeSort(list, tmp, RIGHT, middle+1, right);
   
    int indexL = left;
    int indexR = middle+1;
    int index  = 0;
   
    while(indexL <= middle && indexR <= right)
    {
        if(list[indexL] <= list[indexR])
        {
            tmp[index++] = list[indexL++];
        }
        else
        {
            tmp[index++] = list[indexR++];
        }
    }
   
    //Copy from Left
    for(int i = indexL; i <= middle; i++)
        tmp[index++] = list[i];
    //Copy from Right
    for(int i = indexR; i <= right; i++)
        tmp[index++] = list[i];
   
    //Debug
    printf("[%02d] %c ", g_icount++, type);
    for(int i = 0; i < index; i++)
        printf("%d ", tmp[i]);
    printf("\n");
   
    //Copy to list
    int j;
    for(int i = left, j = 0; i <= right; i++, j++)
        list[i] = tmp[j];   
}
//---------------------------------------------------------------------------
int main(void)
{
    int list[] = {12,15,49,22,15,10};
   
    int max = sizeof(list)/sizeof(int);
   
    int tmp[6];   
   
    mergeSort(list, tmp, LEFT, 0, max-1);
   
    printf("\nResult: ");
    for(int i = 0; i < max; i++)
        printf("%d ", list[i]);
    printf("\n\n");
       
    system("pause");
    return 0;
}
//---------------------------------------------------------------------------