The Secrets and Pitfalls of JavaScript's sort Function

Chris has now become a sorting algorithm expert.

He has mastered Bubble, Selection, Insertion, Quick, Merge, Heap, and even Radix Sort.

"Alright, time to apply this to real work!"

Chris wrote some code to sort an array of numbers.

const numbers = [2, 1, 10, 3, 5];
numbers.sort();

console.log(numbers);
// Expected Result: [1, 2, 3, 5, 10]
// Actual Result:   [1, 10, 2, 3, 5]  <-- ?!?!?!

"Wait, why is 10 appearing before 2? Is JavaScript bad at math?"

Chris was flustered. What's the point of knowing how to implement Quick Sort if he doesn't understand how the sort() function he uses every day actually works?

In the final post of Chapter 2, we will uncover the fatal traps of Array.prototype.sort() that we use like breathing, and the identity of the internal algorithm hidden by the browser.

1. The Trap: Why Treat Numbers as Strings?

If you do not pass an argument (Comparator) to JavaScript's sort(), it defaults to converting all data to Strings and sorting them in Unicode order.

This is why 10 comes before 2. Just as "Apple" appears before "Banana" in a dictionary, the string "10" starts with "1", so it is placed before "2".

Solution: Provide a Comparator

To sort numbers by magnitude, you must provide a comparison function.

// Ascending Order
numbers.sort((a, b) => a - b); 

// Descending Order
numbers.sort((a, b) => b - a);

2. The Secret: Which Algorithm Does the Browser Use?

When we call sort(), what happens inside the browser (engine)?

Quick Sort? Merge Sort?

In the past, it varied by browser. Chrome (V8) used Quick Sort, while Firefox used Merge Sort. This led to a chaotic era where Chrome had 'Unstable Sort' and Firefox had 'Stable Sort'.

However, starting from ECMAScript 2019 (ES10), a spec was added stating "It must be a Stable Sort."

Accordingly, most modern browsers (including the V8 engine) now use an algorithm called TimSort.

TimSort: The Aesthetics of a Hybrid

TimSort is an algorithm created in 2002 by Tim Peters, a core developer of Python.

This guy cleverly mixes Insertion Sort and Merge Sort which we learned earlier.

In other words, sort() is not magic, but a Hybrid combining the strengths of the algorithms we've learned.

3. Caution for React Developers: Immutability

sort() has another trap. It Mutates the Original Array.

const original = [3, 1, 2];
const sorted = original.sort();

console.log(original); // [1, 2, 3] <-- The original has changed!
console.log(sorted);   // [1, 2, 3]
console.log(original === sorted); // true (Same reference)

If you sort state like this in React, you're in trouble. React only re-renders when the object's reference value changes. If you modify the original directly, React won't detect the change, leading to unexpected bugs.

Solution 1: Copy then Sort (Old School)

// Create a copy with the spread operator, then sort.
const sorted = [...original].sort((a, b) => a - b);

Solution 2: toSorted() (New Standard, ES2023)

In 2023, a method was finally added that returns a new sorted array without touching the original.

const sorted = original.toSorted((a, b) => a - b);
console.log(original); // [3, 1, 2] (Preserved)
console.log(sorted);   // [1, 2, 3] (New Array)

If you are a React developer, make it a habit to use toSorted instead of sort.

4. Wrapping up Chapter 2: Beyond Sorting

So far, we have thoroughly dug into 8 sorting algorithms and even JavaScript's internal implementation.

Now you have perfectly mastered how to arrange data in order.

What can you do once the data is sorted? You can "Find the desired data at the speed of light."

If books are sorted in a library, a librarian can find a book in 1 second.

Now it's time to depart for the world of Searching. From the winning strategy of the Up-Down game to the principles of how GPS navigation finds paths.

🔗 References