Stable Sorting In JavaScript

JavaScript 2017 specification states the following about its built-in sorting, “The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order).” What’s a JavaScript programmer to do if a stable sort is needed?

Good examples of stable and unstable sorting

I looked all over the internet for suggestions, but nothing worked. In theory the solution seems simple – in case the two items being compared are equal, compare their index within the array. If index of the first element of the comparison is smaller than the second then don’t swap the array elements. However, the comparison function does not have access to the index of each element within the array. You are now officially stuck. Stable sorting does not seem to be possible with JavaScript built-in sort.

Another possible approach is to add an extra data member to the object, which holds the index within the array being sorted. Sort the array using an unstable sorting algorithm. Run a stabilization pass over the resulting array to fix the stability of all equal elements.

Other frustrated coders have reached this conclusion as well, suggesting implementing Merge Sort instead, which is a good ideas if you need a comparison based sorting algorithm.

However, if you don’t need to compare, such as where unsigned integers are being used as items to sort on – for example, primary keys of the database – then LSD Radix Sort is your friend. It’s stable. It runs in linear time. And, a high performance implementation is available in Faster Sorting in JavaScript

Enjoy, and let me know if it’s helpful.

Further Thoughts

At times stability is not needed. Two such cases are where the array is all numbers, and where primary database keys are used for sorting by. In the first case, there is no difference between numbers, and thus it doesn’t matter if identical numbers are swapped, since it’s impossible to tell the difference between equal numbers. In the second case or sorting by primary database key, these keys are unique, without duplicates, and thus, equal keys will never occur.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s