(NOTE: There is sample code to go along with this article.)
In web applications, a task that often needs to be performed is the sorting of arrays. If you're anything like me, you often use the Array.prototype.sort method to accomplish this task. And who could blame you? It's short, it's easy, its implementation is performant, and it works exactly the way you want it to most of the time. As you can see in the code pictured below, all we have to do is call the "sort" method of our array, passing in a function that compares two elements and returns either 1, -1, or 0 depending on how the elements compare. Nice and easy.
But wait - what do I mean by "it works... most of the time"? Well, let me clarify: it always works, but it won't always work the way you expect it to. For most of us, when we sort an array or list or any other collection, we expect that two items that are considered "equal" should appear in the sorted collection in the same order that they were in in the unsorted collection. For example, if we were sorting an array that contained the integers 6, 3, 3, and 1, we would expect that first 3 to appear before the second 3 in the sorted array. That's called a "stable" sort.
Now, the problem with the Array.prototype.sort method is that different browsers implement it differently. Internet Explorer and Edge always use a stable sort. Firefox uses a stable sort. Even poor, neglected Opera uses a stable sort. But there's a rebel: Google Chrome. Chrome uses a stable sorting algorithm for arrays of length < 10, but for arrays of more than ten items, it uses an unstable QuickSort algorithm. This can lead to unreliable behavior that you might not discover when testing if you don't think to test your code on an array with more than ten items in Chrome.
To be fair, it doesn't matter most of the time whether or not we use a stable sort. If we're just sorting a list of names, we don't really care whether all the Smiths appear in the same order relative to each other after sorting. However, there are some cases where we DO care about the stability of our sort, such as the very simple web application depicted in the below screenshot.
This web application renders an array of "Person" objects, in alphabetical order by first name. To render the array in order, we use the Array.prototype.sort method, passing in a comparison function that only compares the first name, so other properties (such as last name or occupation) have absolutely zero impact on the order in which the items are displayed. Now, if we're only displaying this data one time when first loading the page, it doesn't matter. Where we run into a problem is if we try to re-sort the data and then render it again, because Chrome's unstable sorting algorithm will cause the items to "jump around" when there are multiple items with the same "First Name" property.
In the above screenshot, I've used the text input field in the "First Name" column to change Alec Baldwin's first name to "Steve". In the OnChange event handler for that input, we're re-sorting the array and re-rendering it. What we would EXPECT to see is that the people are displayed in the same order, except that Baldwin now appears at the bottom of the table because his new first name (Steve) should appear last alphabetically - all the other items in the table should appear in the same order relative to each other as before. But that's not what happens: James Bond now appears between James Madison and James Caan, and James Buchanan now appears almost at the top of the list instead of almost at the bottom. Not only is it visually unsettling when items jump around like that unexpectedly, but it also hurts the user experience.
Now, Google has no plans to change their implementation of Array.prototype.sort ever, because they consider it to be working as intended. And I don't blame them - the W3 standard for that method does not specify whether the sort should be stable, so it's left up to each browser developer whether or not to use a stable sorting algorithm. So if you want to ensure that your sorts are always stable, you have to implement your own method of sorting.
The method I recommend for sorting in JavaScript is to create an object or class that will handle sorting for you; you shouldn't override the Array.prototype.sort method for a number of different reasons which won't be covered here.
The above screenshot shows the file "Sorter.js" included in the sample project. It declares an object in my project's namespace called "Sorter", which has several methods. The method that we actually use in our application is "sort". This method takes two parameters: the array that we're sorting, and the function that will be used to compare objects in the array (this function should be identical to the one we would use in Array.prototype.sort). Based on the number of items in the array, the sort method uses one of two sorting methods: if there are fewer than ten items, we use an insertion sort. If there are more than ten items in the array, we use a stable merge sort, which is still one of the faster sorting algorithms. The merge sort algorithm we're using here was adapted from the one shown in this article.
So now, back in our main application logic where we previously were calling the Array.prototype.sort method, we will now call the "sort" method of our Sorter object, like so:
This new method is only slightly less convenient than the prototype sort method, but it allows us to have greater control over how our arrays are sorted, and it greatly reduces the possibility of sorting-related bugs. If we edit items in the web application now, we can see that items with the same value for "First Name" will stay in the same order relative to each other, so items don't "jump around" unexpectedly.
A real-world application of this technique is a time entry web application, where users have a table of time entries with fields such as duration, person's name, and category, and where users can choose to sort by any combination of those fields. Instead of writing a bunch of complicated code to determine when the table should re-sort, or ensuring that if the table is already sorted it doesn't get re-sorted, we can simply use our custom sorting implementation to make sure that items in the table don't get moved around unless they absolutely should.
Learn how DMC can help you with your web development needs.