This holiday season, I discovered a new favorite tradition: Advent of Code. It’s an online advent calendar with two new coding challenges each day. On day 4, I ran into a perplexing problem. I tested my code in every way I could think of, and I was pretty darn sure it worked, but I couldn’t get the right answer.
Why couldn’t I? Well, to find out, let’s flash back a couple months. I was answering questions for one of my first workshops as a teaching fellow. The students were writing two different sorting algorithms: merge sort and bubble sort. There are a number of sorting algorithms out there with different efficiencies, and learning to write them is a good way to build fundamental programming skills. Most developers rarely have to write these algorithms themselves, however, because languages like JavaScript have a built in sorting function. The last question I was asked on that workshop was, “So… under the hood, which algorithm does the JavaScript sort function use?”
“Interesting, ” I said, “let me look that up.”
It turns out that, like many things in JavaScript, the answer is “it depends.” It depends on the engine that JavaScript is running on (in most cases, this is determined by which browser you are using). So, in short, different browsers will interpret the line array.sort() in different ways.
Fast forward a month. It turns out that my solution for day 4 of Advent of Code relied on JavaScript’s sorting function. And my solution made an assumption about that function: that it would use a stable sorting algorithm.
A stable sorting algorithm will take two elements that it sees as equivalent and leave them in the order that it found them. An unstable sorting algorithm makes no such promises. It could leave them in the same order, or it could swap them.
A lot of the time, that makes no difference whatsoever. For example, let’s say you want to sort the following array:
[5, 3, 2, 3, 1, 4, 7]
It doesn’t really matter which 3 comes first in the solution – you will get the same answer either way. An unstable sorting algorithm will do perfectly fine here. But let’s consider a situation in which you are sorting objects instead of numbers. These objects have both a name and an age property, and you want to sort by age.
[{name: 'bob', age: 3}, {name: 'alice', age: 5 }, {name: 'willow', age: 3}]
In this example, an unstable sorting algorithm might tell you Bob comes first, or it might tell you Willow comes first. A stable sorting algorithm will always say that Bob comes first.
And sometimes that matters, especially when you are trying to sort by two keys. For example, if you wanted to sort the above array by age and then alphabetically by name, you would need a stable sorting algorithm. This is essentially what I was doing in day 4 of Advent of Code.
So here’s the thing. Most browsers don’t consistently use a stable sorting algorithm. I was running my code in Node.js, which uses Chrome’s V8 engine, which does not use stable sorting. As soon as I ran my code in Firefox, I was able to get the correct solution. Magic!
Galen E. Corey 