歸并排序：假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到?n / 2?（向上取整）個長度為2或1的有序子序列；再兩兩歸并，如此重復，直到得到一個長度為n的有序序列為止。

歸并排序的平均時間復雜度為O(nlogn)。

// 歸并排序
#include <stdio.h>
#include <malloc.h>

#define N 10 // 數組最大值

// 順序表結構
typedef struct {
    int value[N + 1]; // 順序表中的值
    int length; // 順序表長度
} SqList;

/**
 * 初始化順序表
 * @param L 順序表
 * @param d 存初始值的數組
 */
void InitSqList(SqList *L, int *d) {
    int i;

    for (i = 0; i < N; ++i) {
        L->value[i + 1] = d[i];
    }
    L->length = N;
}

/**
 * 遍歷順序表中元素的值
 * @param L 順序表元素
 */
void Print(SqList L) {
    int i;

    printf("順序表中的值為：");
    for (i = 1; i < L.length; i++) {
        printf("%d, ", L.value[i]);
    }
    printf("%d", L.value[i]);
    printf("\n");
}

/**
 * 將有序的SR[i..m]和SR[m+1 .. n]歸并為有序的TR[i..n]
 * @param SR 需要進行歸并的順序表
 * @param TR 歸并后存值的順序表
 * @param i 起點下標
 * @param m 中間點下標
 * @param n 終點下標
 */
void Merge(int SR[], int TR[], int i, int m, int n) {
    int j, k, t;

    // 依次比較SR中前半部分和后半部分對應下標的值，存入TR中
    for (j = m + 1, k = i; i <= m && j <= n; k++) {
        // 前半部分的對應位置的值小于后半部分
        if (SR[i] < SR[j]) {
            TR[k] = SR[i++]; // 將前半部分的對應位置的值存入TR
        } else { // 后半部分的對應位置的值小于前半部分
            TR[k] = SR[j++]; // 將后半部分的對應位置的值存入TR
        }
    }

    // 將剩余的SR[i..m]復制到TR
    if (i <= m) {
        for (t = 0; t <= m - i; t++) {
            TR[k + t] = SR[i + t];
        }
    }

    // 將剩余的SR[j..n]復制到TR
    if (j <= n) {
        for (t = 0; t <= n - j; t++) {
            TR[k + t] = SR[j + t];
        }
    }
}

/************** 歸并排序（遞歸版）**************/

/**
 * 歸并排序
 * @param SR 需要歸并的順序表
 * @param TR1 存儲歸并后的值的順序表
 * @param s 起點下標
 * @param t 終點下標
 */
void MSort(int SR[], int TR1[], int s, int t) {
    int m;
    int TR2[N + 1]; // 存儲順序表中的臨時數組

    // 如果只剩一個元素
    if (s == t) {
        TR1[s] = SR[s]; // 將SR的s下標的值賦值給TR1
    } else {
        m = (s + t) / 2; // 求出中間點下標
        MSort(SR, TR2, s, m); // 對順序表的前半部分遞歸排序
        MSort(SR, TR2, m + 1, t); // 對順序表的后半部分遞歸排序
        Merge(TR2, TR1, s, m, t); // 合并前半部分和后半部分的值并排序到TR1中
    }
}

/**
 * 調用歸并排序
 * @param L 順序表
 */
void MergeSort(SqList *L) {
    MSort(L->value, L->value, 1, L->length); // 對整個順序表進行歸并排序
}

/***********************************************/

/************** 歸并排序（非遞歸版）**************/

/**
 * 歸并排序（非遞歸）
 * @param SR 需要歸并的順序表
 * @param TR1 存儲歸并后的值的順序表
 * @param s 起點下標
 * @param t 終點下標
 */
void MergePass(int SR[], int TR[], int s, int n) {
    int i = 1;
    int j;

    while (i <= n - 2 * s + 1) {
        // 將子序列兩兩歸并
        Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
        i = i + 2 * s; // 子序列長度加倍
    }

    if (i < n - s + 1) {
        // 歸并最后兩個子序列
        Merge(SR, TR, i, i + s - 1, n);
    } else {
        // 若最后只剩下單個子序列，直接將值賦值給TR
        for (j = i; j <= n; j++) {
            TR[j] = SR[j];
        }
    }
}

/**
 * 調用歸并排序（非遞歸）
 * @param L 順序表
 */
void MergeSort2(SqList *L) {
    int k = 1; // 用來記錄子序列長度
    int *TR = (int *) malloc(L->length * sizeof(int)); // 申請存儲空間

    while (k < L->length) {
        // 將L->value的值歸并到TR中
        MergePass(L->value, TR, k, L->length);
        k = 2 * k; // 子序列長度加倍

        // 將TR的值歸并回L->value中
        MergePass(TR, L->value, k, L->length);
        k = 2 * k; // 子序列長度加倍
    }
}

/***********************************************/

int main() {
    int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20, 102}; // 存初始值的數組
    SqList L; // 順序表

    InitSqList(&L, d); // 初始化順序表
    printf("在進行初始化之后");
    Print(L); // 遍歷順序表

    MergeSort(&L); // 對順序表進行歸并排序
    printf("歸并排序(遞歸)后");
    Print(L); // 遍歷順序表

    InitSqList(&L, d); // 初始化順序表
    MergeSort2(&L); // 對順序表進行歸并排序
    printf("歸并排序(非遞歸)");
    Print(L); // 遍歷順序表

    return 0;
}

運行結果