Contents
  1. 1. 概念
  2. 2. 時間複雜度
  3. 3. 空間複雜度
  4. 4. 穩定性
  5. 5. Code

概念

將數列一直對半切割, 切到最小單位(單一元素), 再左右合併回去, 合併的同時做排序(如以下的動畫)。
和Quicksort一樣是divide & conquer的概念, 但不同的是Merge sort都是對半切割,而Quicksort是依據所選的pivot值分成兩堆(大於pivot的放一堆,小於的放一堆)。


(File from Merge sort wiki, CC BY-SA 3.0)

時間複雜度

每次合併都是O(n),而每次遞迴呼叫都是處理數列的一半O(log2 n),所以總共是O(nlog n)。

Best : O(nlog n)
Average : O(nlog n)
Worst : O(nlog n)

空間複雜度

O(n)

穩定性

穩定

Code

See my code on github.

參考資料:
Mergesort wiki
Sorting algorithm wiki