動機

merge sort as a sorting framework

merge sort其實不用分到最後一個才merge,merge時才sort是因為沒有其他手法,如果有其他sort?

可以直接切成各個小list去sort,之後就是merge

external merge sort

如果記憶體有限,可以把大檔案(list),分成小檔案,把小檔案放到mem做一般的sort

之後把記憶體分成

  1. 放每個小檔案的sublist
  • 各自的buffer為空時就往下讀
  1. 輸出merge結果的list
  • 滿了就放到目標檔案