/* 二路歸并排序算法的源程序*/

#include<stdio.h>

#define MAXNUM 100
#define TRUE 1
#define FALSE 0

typedef int KeyType;
typedef int DataType;

typedef struct {
    KeyType key;       /* 排序碼字段 */
    /*DataType info;           記錄的其它字段 */
} RecordNode;

typedef struct {
    int n;               /* n為文件中的記錄個數，n<MAXNUM */
    RecordNode record[MAXNUM];
} SortObject;

void merge(RecordNode r[], RecordNode r1[], int low, int m, int high) {
    /* r[low]到r[m]和r[m+1]到r[right]是兩個有序段 */
    int i = low, j = m + 1, k = low;
    
    while ( i <= m && j <= high ) {    /* 反復復制兩個段的第一個記錄中較小的 */
        if (r[i].key <= r[j].key)  
            r1[k++] = r[i++];
        else r1[k++] = r[j++];
    }

    while (i <= m) r1[k++] = r[i++];   /* 復制第一個段的剩余記錄 */
    while (j <= high) r1[k++] = r[j++];/* 復制第二個段的剩余記錄 */

}

/* 對 r 做一趟歸并，結果放到 r1 中 */
void mergePass(RecordNode r[], RecordNode r1[], int n, int length) {
    int i = 0, j;                     /* length為本趟歸并的有序子段的長度 */

    while(i + 2*length - 1 < n) {
        merge(r, r1, i, i+length-1, i + 2*length - 1);/* 歸并長length的兩個子段*/
        i += 2*length;
    }
    
    if(i + length - 1 < n - 1)        /* 剩下兩段，后一段長度小于 length */
        merge(r, r1, i, i+length-1, n-1);
    else                              /* 將剩下的一段復制到數組r1 */
        for(j = i; j < n; j++) r1[j] = r[j];
}

void mergeSort(SortObject * pvector) {
    RecordNode record[MAXNUM];
    int length = 1;

    while (length < pvector->n) {
        /* 一趟歸并，結果存放在數組record中*/
        mergePass(pvector->record, record, pvector->n, length);
        length *= 2;
        /* 一趟歸并，結果存回 */
        mergePass(record, pvector->record, pvector->n, length);
        length *= 2;
    }
}

SortObject vector = {8, 49,38,65,97,76,13,27,49};

int main(){
    int i;
    mergeSort(&vector);
    for(i = 0; i < 8; i++)
        printf("%d ", vector.record[i]);
    getchar();
    return 0;
}