前言

Merge Sort是一個很有效率的排序法，利用遞迴的方式達到 $O(nlogn)$ 的複雜度，屬於 stable sorting

概念

原理就是不斷將array切割成左右兩塊，左右兩塊利用遞迴特性繼續切割，直到切到最小單位時，才會開始合併，合併時才真正比較大小做排序，也是Divide and Conquer的運用

流程大概如下：

  1. 將array分成左半部跟右半部
  2. 左半和右半重複做1的動作(遞迴, 不斷切半)
  3. 合併左半右半(不斷合併)

pseudo code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 切割 */
MergeSort(A[1..n])
  if n = 1:
  return A
  m ← n/2
  // 左右兩個array
  Array left[1..m]
  Array right[1..n-m]
  // 將原array的值assign到左右兩個array
  for i from 1 to n:
    left[i] ← A[i]
  for i from 1 to n-m:
	right[i] ← A[m+i]
  // 遞迴
  MergeSort(left)
  MergeSort(right)
  Merge(A, left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 合併, 開始比大小 */
Merge(A[1..n], left[1..n/2], right[1..(n-n/2)])
  i ← 1
  j ← 1
  k ← 1
  // 比較小的就先塞到array A
  while i < leftSize and j < rightSize:
    if left[i] <= right[j]:
      A[k++] ← left[i++]
    else:
      A[k++] ← right[j++]
  // 如果有剩餘的值就全部塞入array A(因為左右兩個array的大小可能不同)
  while i < leftSize:
    A[k++] ← left[i++]
  while j < rightSize:
    A[k++] ← right[j++]

複雜度比較

時間複雜度

Sequence Complexity
Random $O(NlogN)$
Nearly Sorted $O(NlogN)$
Reversed $O(NlogN)$
Few Unique $O(NlogN)$

Merge sort 的時間複雜度在所有情況下都是 ＄O(NlogN)$, 獨立於資料的組成

空間複雜度

因為需要用到額外的 array 來儲存分割的資料作排序，用到 $O(n)$ space
如果用 linked list，則是 $O(logN)$ space

可以到 Toptal 的這個網頁觀看不同 case 的視覺化排序過程