# 3.3.2 - Merge Sort Merge sort為external sorting常用的排序方法之一，可以分為: 1. Iterative Merge Sort 2. Recursive Merge Sort 示意圖: (Run為以排序好的片段資料) ![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIQdh7EEZHr4WZl1fpl%2F-LIQdjAdiTMKAUAhy1vx%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-27%2020.11.05.jpg?alt=media\&token=b98cfb8e-332a-4a09-a412-d8c1f659f806) ### 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 ![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIToDAWLAvalY6gmqMG%2F-LIToGrbtXDHKr-MLkaV%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%2010.53.10.jpg?alt=media\&token=60fdf56c-33ab-4fc1-a8d7-bf3c0c83a6f4) output=3 ![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIToDAWLAvalY6gmqMG%2F-LIToKWt1oGsc5pY7PlX%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%2010.53.55.jpg?alt=media\&token=3338f9db-e8e4-4a97-b060-aff9cbebc692) 2\. Loser Tree: 沿著父點比較 ![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIToDAWLAvalY6gmqMG%2F-LITofNR8twFZIgp-kMV%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%2010.56.21.jpg?alt=media\&token=905758be-8695-47d1-89b1-eba9097e3973) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://garychang.gitbook.io/data-structure/3-search/sophisticated-sorting/3.3.2-merge-sort.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.