歸並排序演算法原理與C語言實現完整指南

歸並排序核心思想

歸並排序採用分治法策略，核心操作是「歸並」——將兩個已排序序列合併為一個有序序列。演算法遞迴將序列不斷二分（或多分）直到單元素，再自底向上合併。

歸並操作步驟

1. 申請空間，大小為兩有序序列長度之和，用於存放合併結果
2. 設定兩指標，初始指向兩序列起始位置
3. 比較兩指標所指元素，較小者放入合併空間，該指標後移
4. 重複步驟3直到某指標到達序列尾
5. 將另一序列剩餘元素直接複製到合併序列尾部

C語言完整實現

/*=============================================================================
 # FileName: Merge_Sort.c
 # Desc: 歸並排序
 # Author: zhangyuqing
 # Created: 2014年6月29日
 # Version: 0.0.1
 =============================================================================*/
#include <stdlib.h>
#include <malloc.h>

// 歸並操作：將 src[low..mid] 和 src[mid+1..high] 合併到 des[low..high]
void merge(int src[], int des[], int low, int high, int mid) {
    int i = low, k = low, j = mid + 1;
    while ((i <= mid) && (j <= high)) {
        if (src[i] < src[j])
            des[k++] = src[i++];
        else
            des[k++] = src[j++];
    }
    while (i <= mid) des[k++] = src[i++];
    while (j <= high) des[k++] = src[j++];
}

// 遞迴排序核心
void MSort(int src[], int des[], int low, int high, int max_size) {
    if (low == high) {
        des[low] = src[low];
    } else {
        int mid = (low + high) / 2;
        int *des_space = (int *)malloc(sizeof(int) * max_size);
        if (NULL != des_space) {
            MSort(src, des_space, low, mid, max_size);
            MSort(src, des_space, mid + 1, high, max_size);
            merge(des_space, des, low, high, mid);
        }
        free(des_space);
    }
}

// 對外介面
void Merge_Sort(int arr[], int low, int high, int len) {
    MSort(arr, arr, low, high, len);
}

int main(void) {
    int arr[10];
    for (int i = 0; i < 10; i++)
        arr[i] = rand() % 100;

    printf("Before sort:\n");
    for (int i = 0; i < 10; i++) printf("%d ", arr[i]);

    Merge_Sort(arr, 0, 10 - 1, 10);

    printf("\nAfter sort:\n");
    for (int i = 0; i < 10; i++) printf("%d ", arr[i]);
    system("pause");
    return 0;
}

執行結果示例

Before sort: 41 67 34 0 69 24 78 58 62 64
After sort: 0 24 34 41 58 62 64 67 69 78
請按任意鍵繼續. . .

複雜度與特性分析

• 時間複雜度： O(n log n)（最好/最壞/平均皆同）
• 空間複雜度： O(n)（需輔助陣列）
• 穩定性： 穩定排序（相等元素相對順序不變）
• 適用場景： 大規模資料、連結串列排序、外部排序

註：本實現每次遞迴都分配臨時空間，可優化為僅分配一次全域暫存陣列以提升效能。