Algorithm of JavaScript “sort()” Function

by

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;}

More Related Contents:

  1. Javascript Array.sort implementation?
  2. How do you sort an array on multiple columns?
  3. Fast stable sorting algorithm implementation in javascript
  4. How do I sort an array of objects based on the ordering of another array?
  5. Efficient way to insert a number into a sorted array of numbers?
  6. Using Canvas to animate a sorting algorithm in JS
  7. Sorting Array with JavaScript reduce function
  8. Remove duplicate objects from an array using javascript
  9. Optimized merge sort faster than quicksort
  10. sort outer array based on values in inner array, javascript
  11. How may I sort a list alphabetically using jQuery?
  12. Efficiently replace all accented characters in a string?
  13. What is the stability of the Array.sort() method in different browsers?
  14. Finding All Combinations (Cartesian product) of JavaScript array values
  15. How to sort an array of objects with jquery or javascript [duplicate]
  16. How to perform case-insensitive sorting array of string in JavaScript?
  17. Sorting options elements alphabetically using jQuery
  18. How to define custom sort function in javascript?
  19. Fastest way to flatten / un-flatten nested JavaScript objects
  20. Packing different sized circles into rectangle – d3.js
  21. Sorting dropdown list using Javascript
  22. How to allow Web Workers to receive new data while it still performing computation?
  23. Sorting of jqGrid (v4.1.2) treegrid not working with Ajacency Model
  24. Sort an array to have specific items first in the array
  25. Sort an array of objects by multiple properties
  26. Sorting strings in descending order in Javascript (Most efficiently)?
  27. Creating an array consisting of the largest values of each sub-array does not work as expected
  28. Two-sum Leetcode explanation, Hashmap, Javascript
  29. Diamond-square algorithm not working (rewrite code from JS to JAVA)
  30. Javascript: Sort array of arrays by second element in each inner array

Leave a Comment