Array.sort 淺析

這篇文章不是談論在 Javascript 原生的 sort 要注意的事項。例如：

;[1, 2, 3, 8, 20, 30, 11].sort()
// [1, 11, 2, 20, 3, 30, 8]

因為預設的 sort 方法會把值轉為 String，並按照 char code 做排序，所以才會出現上面的結果。

今天要來探討 Javascript 的 sort 背後的實作方式。

從 V8 的實作當中，我們可以看到幾個事實：

Array 的 sort 是用 quick sort 排序
在陣列數量小於等於 10 的時候，使用插入排序。

為了簡化 V8 中的代碼，這邊撰寫一個簡單的快速排序代碼：（僅供參考）

function quickSort(arr, p, r) {
  if (p < r) {
    var q = partition(arr, p, r)
    quickSort(arr, q - 1, p)
    quickSort(arr, q + 1, r)
  }
}

function partition(arr, p, r) {
  var x = arr[r]
  var i = p - 1
  for (var j = p; j < r - 1; j++) {
    if (arr[j] <= x) {
      i += 1
      var tmp = a[j]
      arr[j] = a[i]
      arr[i] = tmp
    }
  }
  var tmp = arr[r]
  arr[r] = a[i + 1]
  arr[i + 1] = tmp
}

深入探討：為什麼是快速排序？

快速排序法的實現重點在於如何選擇一個相對好的 pivot，來避免最壞情況的發生。在實際的情況當中，輸入的資料並不一定是隨機的，所以在實務上都會使用 random 的方式來選擇 pivot。

第一個問題是，**為什麼 V8 使用快速排序？**雖然快速排序的平均時間複雜度可以達到 $O(nlogn)$ ，但是最壞情況也有可能達到 $O(n^2)$ 。同時，快速排序並不是一個穩定的演算法，也就是兩個同樣值的資料，在排序之後位置可能會不同。

為什麼不用合併排序？

合併排序簡單可以分為兩大步驟，先把 array 分解後再調用 merge 不斷合併。不僅平均、最壞、最好時間複雜度都可以達到 $O(nlogn)$ ，演算法本身也是穩定的，為什麼不採用呢？

In-place

我們在 quick sort 當中，並不需要對 array 做合併的動作，也就是整個演算法可以不另外耗費空間完成，而 merge sort 需要 $O(n)$ 的空間。因此儘管快速排序有上述的情況發生，但在實務上他仍然是一個相當好的選擇。

我們可以透過 randomize 的方式（關於如何隨機選取 pivot，實際上還能夠寫一大篇文章來解釋），來避免 $O(n^2)$ 的情形發生。

Stable

不過儘管如此，我們還是沒辦法解決 stable 的問題，雖然在大部分的場景當中可能並不重要（畢竟資料排序通常都是由後端實作），不過如果真的碰到時，這就是非常重要的考量了。

並不是每個瀏覽器的實作都是用 Quicksort

插入排序

如果仔細看一下 V8 的原始碼，會發現這一段：

 while (true) {
  // Insertion sort is faster for short arrays.
  if (to - from <= 10) {
    InsertionSort(a, from, to);
    return;
  }

咦，為什麼在陣列數量小於等於 10 的時候要用插入排序法呢？

要理解原因，我們先回想一下插入排序的原理。插入排序跟撲克牌整理牌的方式很像，每次拿起一張牌，找到一個最適當位置放入，每次的要插入的牌組都是已經整理好的，可以達到原址排序。

function insertionSort(arr) {
  for (var j = 1; j < arr.length; j++) {
    var key = arr[j]
    var i = j - 1
    while (i >= 0 && arr[i] > key) {
      arr[i + 1] = arr[i]
      i = i - 1
    }
    arr[i + 1] = key
  }
  return arr
}

插入排序雖然跟氣泡排序擁有相同的時間複雜度，不過在交換次數上有很大的不同，氣泡排序有 $O(n^2)$ 的交換次數，而插入排序最多只需要 $O(n)$ 。

回到最剛開始的問題，為什麼在陣列數量小於等於 10 的時候要用插入排序法呢？

對於小數量的陣列而言，如果已經排序好，或是相當接近有序的陣列，插入排序法是唯一可以達到時間複雜度 $O(n)$ 的演算法。這是相當有效率的一件事。

結論

因為在工作上需要排序，因此開始深入理解了原生的 sort 在背後做了哪些事情。除了要注意 js 會預設轉為字串比較之外，在處理資料量大的陣列時，理解背後的實作方式就顯得相當重要。

同時我們也了解到，不同的排序演算法都有其適合的場景，在使用 sort 的時候要記得：

Quick sort 在實務上通常有最好的結果，但要注意 quick sort 並不是穩定的演算法
Merge sort 雖然能夠達到 $O(nlogn)$ 的時間複雜度，但是需要額外 $O(n)$ 的空間做 merge
Insertion sort 在小數量的陣列排序上有不錯的效果，最好情形可以在 $O(n)$ 比較完成。