9 months ago

Sorting (placing a collection of items in order) is one of the most common operations in information processing. Arrays are the most common data structure that holds objects we want to sort (collections). So naturally, most modern programming languages provide built-in sort methods to sort arrays. And they are usually very easy and intuitive to use.
In Python for example,

a = sorted ([1, 100,21,9])
print a

will print out the sorted array [1,9,21,100]

In Swift, the code can be even a bit "cute" with emojis!

let 💯 : [Int] = [1,100, 21,9];
print (💯.sorted ())

But Javascript's sort has a mind of its own:

console.log([1,100,21,9].sort())

will printout [ 1, 100, 21, 9 ]
A big oops

Why?

In Javascript, the default sort order i.e. the logic used to determine if an item is greater than, equal to or less than another item uses the ordering of the Unicode strings. The Unicode string '100' is smaller than the Unicode string '21'. Adopting the Unicode as a default sorting order works well with string data but it clearly messes up the sorting of numbers.

The fix

In order for the sort to work correctly with numbers in Javascript we have to override the default ordering by sending a compare function to its built in sort as a parameter. When a compare function is supplied, the sorting order is determined by the return values of the compare function. The compare function has a very specific format and strict requirements.

The requirements

  1. It must have two parameters (say a and b)
  2. It must return a value that is either less than 0, or greater than 0 or equal to 0
  3. It must always return the same value when given a specific pair of elements a and b as its two argument

The override behavior

  • if the compare function returns a value that is less than 0, in the overridden Javascript sort, a comes first.
  • if the compare function returns a value that is greater than 0, in the overridden Javascript sort, b comes first
  • if the compare function returns 0, Javascript should leave a and b unchanged with respect to each other (but sorted with respect to all other specified elements). Note: the ECMAscript standard does not guarantee this behavior, and thus not all browsers respect this.

If you are an experienced Javascript programmer who is familiar with the advanced concepts of Javascript like callback, overloading, function as a first class object etc. the process is actually quite intuitive. But for a newbie it may appear a bit daunting. While we highly recommend you read through this post and follow the links in it, if you are in a hurry to sort your numbers correctly here's the code 😇:

TL;DR: i.e. the code

console.log("% sorted ", [1,100,21,9].sort(compare))
function compare (a, b) {
   if (a < b) {
    return -1;
  }
  if (a > b) {
    return 1;
  }
  return 0;
}


In the code above we are overriding Javascript's default sort order by supplying the compare function. Now instead of using its default sort order to compare and order elements in an array, sort will use the compare function we have provided. Given two numbers, our compare function will return -1, if a is less than b, 1 if a > b and 0 if they are equal.
Therefore by the override behavior described above a will be indexed lower than b if a < b, a will be indexed higher than b if a > b. Thus the sort will work for numbers.

Here is an excellent MDN article explaining the details.

Because we are dealing with numbers, returning the value of a-b has the same effect as spelling out the three cases a > b, a < b and a == b as we have done above. We can make our compare function anonymous and use the a-b pattern to make it a bit more compact like the following:

console.log ([1,100,21,9].sort(function (a,b)  {return a-b})) //ascending

console.log ([1,100,21,9].sort(function (a,b) {return b-a})) //descending


// if you have support for => functions es6

console.log ([1,100,21,9].sort((a,b) => {return a-b})) //ascending

console.log ([1,100,21,9].sort((a,b) => {return b-a})) //descending


The good that comes out of this "pain"

OK, that is a lot to go through to sort a few numbers. We agree! But once you get used to the pattern it will become second nature. Being able to provide a customized compare function to override sort is a very powerful programming tool. We will see one example of it in action in this blog.

Setting up MongoDB on Cloud 9 - mostly for Node/Express users →