演算法 - 合併排序法 ( merge sort )

合併排序（Merge sort)(另譯：歸併排序）是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

歸併操作的過程如下：

1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3.比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
4.重複步驟3直到某一指針達到序列尾
5.將另一序列剩下的所有元素直接複製到合併序列尾


時間複雜度：O(n logn)
空間複雜度：O(n)

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

public void sort(int n, int[] s)
{
    if (n > 1)
    {
        int left = n / 2, right = n - left;
        int[] l = new int[left];
        int[] r = new int[right];
        for (int i = 0; i < left; i++)
            l[i] = s[i];
        for (int i = 0; i < right; i++)
            r[i] = s[left + i];
        sort(left, l);
        sort(right, r);
        merge(left, right, l, r, s);
    }
}

void merge(int left, int right, int[] l, int[] r, int[] s)
{
    int i = 0, j = 0, k = 0;

    while (i < left && j < right)
    {
        if (l[i] < r[j])
        {
            s[k] = l[i];
            i++;
        }
        else
        {
            s[k] = r[j];
            j++;
        }
        k++;
    }
    if (i >= left)
        for (int m = j, c = 0; m < right; m ++, c ++)
            s[k + c] = r[m];
    else
        for (int m = i, c = 0; m < left; m ++, c ++)
            s[k + c] = l[m];
}

回首頁