> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/3-search/sophisticated-sorting/3.3.2-merge-sort.md).

# 3.3.2 - Merge Sort

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

1. Iterative Merge Sort
2. Recursive Merge Sort

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

![](/files/-LIQdjAdiTMKAUAhy1vx)

### 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:&#x20;

  * Avg/Best/Worst Case: $$O(nlogn)$$&#x20;

  &#x20;  $$T(n) = T(\frac{n}{2})+T(\frac{n}{2})+C\times n$$&#x20;
* Space Complexity: $$O(n)$$&#x20;

  &#x20;  $$\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)$$&#x20;
   2. 經過k-1次比較決定出root $$\Rightarrow O(k)$$&#x20;
   3. 輸出root到新的run，在決定新的root $$\Rightarrow$$比較次數為高度-1 $$O(log\_2k)$$，總共花 $$O(nlog\_2k)$$&#x20;
   4. Time Complexity: $$O(k)+O(nlogk)$$&#x20;

示意圖:

output=2

![](/files/-LIToGrbtXDHKr-MLkaV)

output=3

![](/files/-LIToKWt1oGsc5pY7PlX)

&#x20; 2\. Loser Tree: 沿著父點比較

![](/files/-LITofNR8twFZIgp-kMV)