JavaScript Sort

When I first began coding in JavaScript, I was very confused by the output of the built-in Array.sort method when I applied it to an array of integers. Once I dug into the documentation, I learned that the method is designed to accommodate all data types; in order to do this, it converts inputs to Strings and sorts lexicographically. Here's an example of an integer array and sorted output:

let numArr = [5, 35, 450, 1289, 2738];
console.log(numArr.sort());
...
-> [1289, 2738, 35, 450, 5]

JavaScript's sort method behaves this way because JS does not impose strong typing; in other words, JS does not require that variables are declared with a specific data type.

This is a feature of the language which allows flexibility; JS will implicitly convert variables of different data types to be of the same type, so they can be plugged into functions and handled similarly. (Recall: another common instance in which weak typing comes in handy is JS double equals, which compares values but not type, e.g. "2" == 2.)

However, weak typing can cause confusion in some cases, like Array.sort. If a compare function is not specified, the items in the array are all converted to strings. Therefore, our earlier example of integers 1289 & 5, become strings '1289' & '5'.

In order to achieve the desired behavior, you just need to specify a compare function. A compare function is an optional argument passed to the sort method that instructs the sort algorithm to sort using specific logic. The compare function that allows for ascending numeric sort is:

function compareNumbers(a, b) {
  return a - b;
}

When we apply this compare function to our integer array from earlier, we could include the same logic in 'arrow function' form:

let numArr = [5, 35, 450, 1289, 2738];
console.log(numArr.sort((a, b) => a - b);
...
-> [5, 35, 450, 1289, 2738]

For a descending numeric sort I would reverse 'a' & 'b':

let numArr = [5, 35, 450, 1289, 2738];
console.log(numArr.sort((a, b) => b - a);
...
-> [2738, 1289, 450, 35, 5]

As I started digging around, I also began to wonder which sorting algorithm was implemented in the underlying code. After some searching, I found a 17-year-old bug filed by Mozilla to use MergeSort by default. Interestingly, though, even this isn't as straightforward as it seems.

Different engines use different implementations for Array.sort. WebKit's implementation chooses which sorting algorithm to use based on the input type; for example, integers are sorted using C's QuickSort implementation, whereas Strings are sorted with MergeSort.

This is particularly interesting from the perspective of runtime analysis; while MergeSort and QuickSort have the same lower bound (i.e. best case runtime) of Omega(n log n), QuickSort's upper bound (i.e. worst case runtime) is much greater at O(n ** 2). However, QuickSort's efficiency relies on probability; you'll only encounter the worst case runtime if you continuously (randomly) select the smallest or largest element of the list as the pivot point.

Side note: for anyone interested in learning more about sorting algorithms, I recommend starting with VisuAlgo for visualizations.

After coming back up from the Internet rabbit hole on Array.sort, I learned how much can be gained from understanding the implementation details of built-in functions. It can be easy to take existing JS methods for granted, but digging into the details reveals the thought and complexity involved.

Resources

1. Wikipedia reference: Strong and weak typing
2. MDN documentation: Array.prototype.sort()
3. Stack Overflow: JavaScript Array.sort implementations
4. Tutorialspoint: Array#sort implementations
5. Wikipedia reference: Quicksort
6. Big O Cheat Sheet
7. Sorting algorithm visualizations: VisuAlgo