3.3.2 - Merge Sort

Merge sort為external sorting常用的排序方法之一，可以分為:

1. Iterative Merge Sort

2. Recursive Merge Sort

示意圖: (Run為以排序好的片段資料)

1. Iterative Merge Sort

e.g. 2-way merge sort

$5,\ 3,\ 7,\ 4,\ 10,\ 9,\ 1,\ 8,\ 6,\ 13\\ ([5],\ [3]),\ ([7],\ [4]),\ ([10],\ [9]),\ ([1],\ [8]),\ ([6],\ [13])\\ ([3,\ 5],\ [4,\ 7]),\ ([9,\ 10],\ [1,\ 8]),\ [6,\ 13]\\ ([3,\ 4,\ 5,\ 7],\ [1,\ 8,\ 9,\ 10]),\ [6,\ 13]\\ ([1,\ 3,\ 4,\ 5,\ 7,\ 8,\ 9,\ 10],\ [6,\ 13])\\ [1,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10,\ 13]$

• Time Complexity: $O(n\log n)$

  $\Rightarrow$ 每進行merge一次需花 $O(n)$，總共進行 $\log_2 n$回合(Binary Tree高度)

2. Recursive Merge Sort

將資料一分為二，直到分為每一筆資料中只有一個Data，再進行Merge、比較。

void Merge(char *arr, int front, int mid, int end){
    
    char LeftSubArray[mid-front+1];
    char RightSubArray[end-mid+1];
    strncpy(LeftSubArray, arr+front, mid-front+1); //取出左半邊的資料
    strncpy(RightSubArray, arr+mid+1, end-mid);    //取出右半邊的資料

    int MAX = 100;        //將陣列的最後一個設為最大值防止溢位
    LeftSubArray[mid-front+1] = MAX;
    RightSubArray[end-mid] = MAX;

    int idxLeft = 0, idxRight = 0;    //進行排序，比較左右半邊的資料並填入陣列中
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] <= RightSubArray[idxRight]) {
            arr[i] = LeftSubArray[idxLeft];
            idxLeft++;
        }
        else{
            arr[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void Sort(char *arr, int front, int end){

    if (front < end) {
        int mid = (front+end)/2;
        Sort(arr, front, mid);//排序左半邊
        Sort(arr, mid+1, end);//排序右半邊
        Merge(arr, front, mid, end);//進行merge排序
    }
}

• Time Complexity:

  • Avg/Best/Worst Case: $O(nlogn)$

  $T(n) = T(\frac{n}{2})+T(\frac{n}{2})+C\times n$

• Space Complexity: $O(n)$

  $\Rightarrow$ 需要一個額外與Data一樣大小的空間來暫存合併的結果

Merge sorting is a stable sorting method.

3. K-way Merge Sort

比較k個run中的資料，從k個資料中選出最小值，所花時間為 $O(k)$，若每個run中的資料總數為n，則總共需花掉的時間為 $O(n·k)$ 。

• Selection Tree: 改善上述不具效率的方法

1. Winner Tree

   1. 從k個run中複製最小值到leaf $\Rightarrow O(k)$

   2. 經過k-1次比較決定出root $\Rightarrow O(k)$

   3. 輸出root到新的run，在決定新的root $\Rightarrow$比較次數為高度-1 $O(log_2k)$，總共花 $O(nlog_2k)$

   4. Time Complexity: $O(k)+O(nlogk)$

示意圖:

output=2

output=3

2. Loser Tree: 沿著父點比較