3.3.2 - Merge Sort
Last updated
Last updated
Merge sort為external sorting常用的排序方法之一,可以分為:
Iterative Merge Sort
Recursive Merge Sort
示意圖: (Run為以排序好的片段資料)
e.g. 2-way merge sort
將資料一分為二,直到分為每一筆資料中只有一個Data,再進行Merge、比較。
Time Complexity:
Merge sorting is a stable sorting method.
Selection Tree: 改善上述不具效率的方法
Winner Tree
示意圖:
output=2
output=3
2. Loser Tree: 沿著父點比較
Time Complexity:
每進行merge一次需花 ,總共進行 回合(Binary Tree高度)
Avg/Best/Worst Case:
Space Complexity:
需要一個額外與Data一樣大小的空間來暫存合併的結果
比較k個run中的資料,從k個資料中選出最小值,所花時間為 ,若每個run中的資料總數為n,則總共需花掉的時間為 。
從k個run中複製最小值到leaf
經過k-1次比較決定出root
輸出root到新的run,在決定新的root 比較次數為高度-1 ,總共花
Time Complexity: