A Brief Analysis of Array.sort

A Brief Analysis of Array.sort

This article is not about the typical pitfalls to watch out for with native JavaScript sort. For example:

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

Because the default sort method converts values to strings and sorts them according to character codes, we end up with the result above.

Today, we’re going to explore how JavaScript’s sort is implemented under the hood.

From V8’s implementation, we can observe a few key facts:

• Array sort uses quicksort.
• When the array length is less than or equal to 10, it falls back to insertion sort.

To simplify the code in V8, here is a basic implementation of quicksort (for reference only):

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
}

Deep Dive: Why Quicksort?

The key to implementing quicksort lies in selecting a relatively good pivot to avoid worst-case scenarios. In real-world situations, input data is not necessarily random, so practical implementations often use randomization techniques to pick the pivot.

The first question is: Why does V8 use quicksort? Although quicksort’s average time complexity reaches $O(nlogn)$, its worst-case scenario can degrade to $O(n^2)$. Furthermore, quicksort is not a stable sorting algorithm, meaning two elements with equal values may not maintain their relative order after sorting.

Why Not Merge Sort?

Merge sort can be broadly divided into two major steps: dividing the array and repeatedly calling merge to combine them. Not only can its average, worst, and best-case time complexity all reach $O(nlogn)$, but the algorithm itself is also stable. Why not adopt it?

In-place

In quicksort, we don’t need to perform merge operations on arrays, which means the entire algorithm can run in-place without requiring extra space, whereas merge sort requires $O(n)$ space. Therefore, despite the aforementioned drawbacks, quicksort remains an excellent choice in practice.

We can mitigate the $O(n^2)$ worst-case scenario through randomization (how to randomly pick a pivot could easily be an entire article in itself).

Stability

Even so, we still cannot resolve the stability issue. While this may not matter in many scenarios (after all, data sorting is often handled on the backend), when it does come up, it becomes a crucial consideration.

Not all browser implementations use Quicksort

Insertion Sort

If you take a close look at V8’s source code, you will find this snippet:

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

Wait, why use insertion sort when the array has 10 or fewer elements?

To understand why, let’s first recall how insertion sort works. Insertion sort is much like sorting playing cards in your hand: each time you pick up a card, you find the most suitable position to insert it into an already-sorted hand, achieving an in-place sort.

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
}

Although insertion sort shares the same time complexity as bubble sort, there is a significant difference in the number of swaps: bubble sort has $O(n^2)$ swaps, while insertion sort requires at most $O(n)$.

Returning to the original question: Why use insertion sort when the array has 10 or fewer elements?

For small arrays—especially those that are already sorted or nearly sorted—insertion sort is the only algorithm that can achieve a time complexity of $O(n)$. This makes it exceptionally efficient.

Conclusion

Needing to sort data at work led me to look deeper into what native sort does under the hood. Aside from remembering that JavaScript converts values to strings by default for comparison, understanding the underlying implementation becomes quite important when dealing with large datasets.

We also learned that different sorting algorithms each have their ideal use cases. When using sort, keep in mind:

• Quicksort generally delivers the best results in practice, but keep in mind that it is not a stable algorithm.
• Merge sort achieves $O(nlogn)$ time complexity across all cases, but requires an extra $O(n)$ space for merging.
• Insertion sort performs well on small arrays, completing in $O(n)$ comparisons in the best case.