A Brief Analysis of Array.sort

This article does not discuss the nuances of the native JavaScript sort method. For example:

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

The default sort method converts values to strings and sorts them according to their character codes, which explains the above result.

Today, we will explore the implementation of sort in JavaScript.

From the implementation in V8, we can observe a few key facts:

• The sort method for arrays uses quicksort.
• When the number of elements in the array is less than or equal to 10, it employs insertion sort.

To simplify the code from V8, here is a basic implementation of quicksort for reference:

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 = arr[j]
      arr[j] = arr[i]
      arr[i] = tmp
    }
  }
  var tmp = arr[r]
  arr[r] = arr[i + 1]
  arr[i + 1] = tmp
}

In-Depth Discussion: Why Quicksort?

The essence of quicksort's implementation lies in selecting a relatively good pivot to avoid the worst-case scenario. In real-world scenarios, the input data is often not random, which is why a randomized approach is commonly used to select the pivot.

The first question is, Why does V8 use quicksort? While quicksort has an average time complexity of $O(n \log n)$, its worst-case complexity can reach $O(n^2)$. Additionally, quicksort is not a stable algorithm, meaning that two equal values may end up in different positions after sorting.

Why Not Merge Sort?

Merge sort can be simply divided into two main steps: first, break down the array, and then repeatedly merge. It achieves an average, worst, and best-case time complexity of $O(n \log n)$, and the algorithm itself is stable. So why not use it?

In-place

In quicksort, we do not need to perform a merge operation on the array, allowing the entire algorithm to complete without additional space, whereas merge sort requires $O(n)$ space. Therefore, despite the aforementioned drawbacks of quicksort, it still remains a very good choice in practice.

We can use a randomized method (which could merit a lengthy discussion on how to randomly select a pivot) to avoid the $O(n^2)$ scenario.

Stability

However, despite these advantages, we cannot resolve the stability issue. While it may not be critical in most scenarios (after all, data sorting is typically implemented by the backend), it becomes a significant consideration when it arises.

Not every browser implementation uses Quicksort.

Insertion Sort

If we take a closer look at the V8 source code, we can find this snippet:

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

Hmm, why does it use insertion sort when the array size is less than or equal to 10?

To understand the reason, let’s recall the principle of insertion sort. Insertion sort is akin to organizing a deck of playing cards. Each time you pick up a card, you find the most appropriate position to insert it, and the cards you’re inserting into are already sorted, achieving in-place sorting.

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 has the same time complexity as bubble sort, it differs significantly in the number of swaps required. Bubble sort can have $O(n^2)$ swaps, while insertion sort requires at most $O(n)$.

Returning to the original question, Why does it use insertion sort when the array size is less than or equal to 10?

For small arrays, if they are already sorted or nearly sorted, insertion sort is the only algorithm that can achieve a time complexity of $O(n)$. This is highly efficient.

Conclusion

Due to the need for sorting in our work, I began to delve deeper into what happens behind the scenes with the native sort method. Besides being aware that JavaScript defaults to string comparison, understanding the underlying implementation becomes crucial when handling large arrays.

We also learned that different sorting algorithms have their ideal scenarios. When using sort, remember:

• Quicksort typically yields the best results in practice, but keep in mind that it is not a stable algorithm.
• Merge sort can achieve a time complexity of $O(n \log n)$, but it requires an additional $O(n)$ space for merging.
• Insertion sort performs well for small arrays, achieving a best-case time complexity of $O(n)$.