Algorithm of JavaScript "sort()" Function

Question

Recently when I was working with JavaScript "sort()" function, I found in one of the tutorials that this function does not sort the numbers properly. Instead to sort numbers, a function must be added that compares numbers, like the following code:-

<script type="text/javascript">
function sortNumber(a,b)
{
    return a - b;
}

var n = ["10", "5", "40", "25", "100", "1"];
document.write(n.sort(sortNumber));
</script>

The output then comes as:-

1,5,10,25,40,100

Now what I didn't understand is that why is this occurring & can anybody please tell in details as to what type of algorithm is being used in this "sort()" function? This is because for any other language, I didn't find this problem where the function didn't sort the numbers correctly.

Any help is greatly appreciated.

Answer 1

To answer your question on how the sorting function works, I will explain it in detail. As has been said in most of the answers here, calling only sort() on an array will sort your array using strings. Converting your integers to strings as well. Blech!

If you think of your items as characters instead of numbers it makes sense that it would be sorted that way. A good way to see this is to assign letters to your numbers.

//0 = a
//1 = b
//2 = c
//4 = e
//5 = f
//These two arrays are treated the same because they're composed of strings.
var nums  = ["10", "5", "40", "25", "100", "1"];
var chars = ["ba", "f", "ea", "cf", "baa", "b"];

//Here we can see that sort() correctly sorted these strings. Looking at the
//alphabetical characters we see that they are in the correct order. Looking
//at our numbers in the same light, it makes sense that they are sorted
//this way as well. After all, we did pass them as strings to our array.
chars.sort(); //["b", "ba", "baa", "cf", "ea", "f"]
nums.sort();  //["1", "10", "100", "25", "40", "5"]

//The bad part of sort() comes in when our array is actually made up of numbers.
var nums = [10, 5, 40, 25, 100, 1];
nums.sort(); //[1, 10, 100, 25, 40, 5]

//As a result of the default sorting function converting numbers to strings 
//before sorting, we get an unwanted result. We can fix this by passing in our 
//own function as a parameter to sort().

You can control how to sort the array by passing your own function as a parameter to the sort() function. This is nice, but unless you know how the sort() function works, it really won't do you any good.

sort() will call your function multiple times to re-arrange the array. Depending on what is returned from your function tells sort() what to do with the items in the array. If a negative number or 0 is returned, no re-arranging happens. If a positive number is returned, the two items switch place. sort() keeps track of which numbers it has already tested, so it doesn't end up testing numbers again later after it has switched the items around. If sort() re-arranges items, it will move back one position and see if it has tested these two items before. If it hasn't it will test them. If it has, it will continue on without running your function on them.

Sorting Numbers

Let's take a simple example and I will walk you through it:

var arr = [50, 90, 1, 10, 2];

arr = arr.sort(function(current, next){
    //My comments get generated from here
    return current - next;
});

//1 : current = 50, next = 90
//  : current - next (50 - 90 = -40)
//  : Negative number means no re-arranging
//  : Array now looks like [50, 90, 1, 10, 2]
//
//2 : current = 90, next = 1
//  : current - next (90 - 1 = 89)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [50, 1, 90, 10, 2]
//
//If sort() didn't backtrack, the next check would be 90 and 10, switch those 
//positions, check 90 and 2, and switch again. Making the final array
//[50, 1, 10, 2, 90], not sorted. But lucky for us, sort() does backtrack.
//
//3 : current = 50, next = 1
//  : current - next (50 - 1 = 49)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 50, 90, 10, 2]
//
//If sort() wasn't smart, it would now check 50 and 90 again. What a waste! 
//But lucky for us again, sort() is smart and knows it already made this 
//check and will continue on.
//
//4 : current = 90, next = 10
//  : current - next (90 - 10 = 80)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 50, 10, 90, 2]
//
//sort() backtracks one position and sees that it has not checked 50 and 10
//
//5 : current = 50, next = 10
//  : current - next (50 - 10 = 40)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 10, 50, 90, 2]
//
//sort() backtracks one position and sees that it has not checked 1 and 10
//
//6 : current = 1, next = 10
//  : current - next (1 - 10 = -9)
//  : Negative number means no re-arranging
//  : Array now looks like [1, 10, 50, 90, 2]
//
//sort() remembers that it already checked 10 and 50 so it skips ahead
//sort() remembers that it already checked 50 and 90 so it skips ahead
//
//7 : current = 90, next = 2
//  : current - next (90 - 2 = 88)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 10, 50, 2, 90]
//
//sort() backtracks one position and sees that it has not checked 50 and 2
//
//8 : current = 50, next = 2
//  : current - next (50 - 2 = 48)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 10, 2, 50, 90]
//
//sort() backtracks one position and sees that it has not checked 10 and 2
//
//9 : current = 10, next = 2
//  : current - next (10 - 2 = 8)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 2, 10, 50, 90]
//
//sort() backtracks one position and sees that it has not checked 1 and 2
//
//10: current = 1, next = 2
//  : current - next (1 - 2 = -1)
//  : Negative number means no re-arranging
//  : Array now looks like [1, 2, 10, 50, 90]
//
//sort() remembers that it already checked 2 and 10 so it skips ahead
//sort() remembers that it already checked 10 and 50 so it skips ahead
//sort() remembers that it already checked 50 and 90 so it skips ahead
//sort() has no more items to check so it returns the final array
//which is [1, 2, 10, 50, 90]

If you wanted the array to be ordered in descending order [90, 50, 10, 2, 1] you can just change the return statement from return current - next; to return next - current; like so:

var arr = [50, 90, 1, 10, 2];

arr = arr.sort(function(current, next){
    //My comments get generated from here
    return next - current;
});

//1 : current = 50, next = 90
//  : next - current (90 - 50 = 40)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [90, 50, 1, 10, 2]
//
//2 : current = 50, next = 1
//  : next - current (1 - 50 = -49)
//  : Negative number means no re-arranging
//  : Array now looks like [90, 50, 1, 10, 2]
//
//etc.

It does not matter if your array is composed of "string numbers" "5" or just numbers 5 when using your own function to sort numbers. Because when JavaScript is doing math, it treats "string numbers" as numbers. i.e. "5" - "3" = 2

Sorting Strings

When you sort strings, you can compare them using the > and < (greater-than and less-than) operators. The greater-than operator sorts the string by ascending order (A-Z, 1-9), and the less-than operator sorts by descending order (Z-A, 9-1). Different browsers use different sorting algorithms so when sorting by strings you have to make sure you are returning either 1 or -1, not true or false.

For example, this works in Chrome and FF, but not IE:

var arr = ['banana', 'orange', 'apple', 'grape'];

arr = arr.sort(function(current, next){
    return current > next;
});

The way to make sure your sorting algorithm works in every browser, use the ternary operator.

var arr = ['banana', 'orange', 'apple', 'grape'];

arr = arr.sort(function(current, next){
    return current > next? 1: -1;
});

When changing the way you're sorting (by ascending or descending order), in addition to changing the operators, you could keep the same operator and switch the current and next variables as we did when sorting numbers. Or since we are using the ternary operator, you could switch the 1 and -1.

Sorting Objects

Here is a neat trick that I thought I'd add in here. You can sort objects if you add them to an array and use their key to compare. Here is an example.

var arr = [
    {id: 2, name: 'Paul'},
    {id: 1, name: 'Pete'}
];

//sort numerically
arr = arr.sort(function(current, next){
    return current.id - next.id;
});
//Array now looks like [{id: 1, name: 'Pete'}, {id: 2, name: 'Paul'}]

//sort alphabetically
arr = arr.sort(function(current, next){
    return current.name > next.name? 1: -1;
});
//Array now looks like [{id: 2, name: 'Paul'}, {id: 1, name: 'Pete'}]

Recap

To sort numbers
in ascending order (1, 2, 3...): function(a, b){return a - b;}
in descending order (9, 8, 7...): function(a, b){return b - a;}

To sort strings
in ascending order (A, B, C...): function(a, b){return a > b? 1: -1;}
in descending order (Z, Y, X...): function(a, b){return b > a? 1: -1;}

To sort objects add them to an array,
then sort by key: function(a, b){return a.key - b.key;}