If you've ever looked at the syntax for sorting an array in JavaScript, you may have wondered how it works under the hood. The ECMAScript Spec is (intentionally, I would guess) vague about it.

Perform an implementation-dependent sequence of calls to the [[Get]] and [[Set]] internal methods of [...] - ECMAScript 2015 Specification

So it's up to the implementation authors. Got it. Let's first take a look at how to use the .sort method in JavaScript, then see how V8 chooses to implement it, and analyze its time and space complexity.

TL;DR

For arrays containing 10 or fewer elements, time complexity of .sort is O(n^2), and space complexity is O(1). For longer arrays time complexity is Θ(n log(n)) (average case), and space complexity is O(log(n))

Using .sort

.sort accepts an optional callback that takes 2 parameters and returns either a negative number, a positive number, or 0. The two parameters are the two elements of the array that are being compared. If the return value is positive, the first parameter is placed after the second. If it's negative, the first parameter is placed before the second. And if it's 0, they are equal. The callback will continually execute until the array is sorted. To make it less abstract, here's two examples.

const ascending = (a, b) => return a - b;

const descending = (a, b) => return b - a; 

The first function will sort an array from lowest value to highest, and the second function will sort an array from highest value to lowest. In .ascending, the expression (a - b) will evaluate to a positive number if a is greater than b, so the underlying sorting algorithm knows to put a after b. The opposite is true for the descending function. In both functions, 0 will be the return value if a and b are equal.

const x = [4,3,5,1,9,2,7,7,2] // Our initial unsorted array
x.sort(ascending) // => [1, 2, 2, 3, 4, 5, 7, 7, 9]
x.sort(descending) // => [9, 7, 7, 5, 4, 3, 2, 2, 1]

The V8 Implementation

V8 is Google's JavaScript engine that powers Chrome and Node. Their implementation is quite clever. If we go directly to the master branch of the V8 source code we can see that Quick Sort is used by default. A check is made, however, to see if the length of the array to be sorted is less than or equal to 10.

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

So the V8 engine uses Insertion Sort for super short arrays and Quick Sort for longer arrays. Interesting.

Time and Space Complexity.

There's nothing magical going on in the QuickSort and InsertionSort functions in V8. QuickSort appears to use a simple two-way partition so its time complexity can be described as Θ(n log(n)) in the average case. Quicksort's space complexity is O(log(n)).

InsertionSort uses the usual nested for loop so its time complexity is O(n^2) and its space complexity is O(1) because it sorts the array in place.