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

Well, if you are sorting the following list, it contains only strings:

var n = ["10", "5", "40", "25", "100", "1"];

So I would expect any language would compare them as strings, thus resulting in a sort order of:

var n = ["1", "10", "100", "25", "40", "5"];

Which necessitates your code to use a custom sort (as you have done) to cast the strings back to integers for the purposes of sorting.

Edit

As Pointy mentioned, by default the JavaScript sort() method sorts elements alphabetically, including numbers:

By default, the sort() method sorts the elements alphabetically and ascending. However, numbers will not be sorted correctly (40 comes before 5). To sort numbers, you must add a function that compare numbers.

Simply amazing... so a custom sort is required even for an array of integers.

Answer 2

And what if your n is defined as:

var n = [10, 5, 40, 25, 100, 1]; 

Answer 3

The problem lies with the use of strings to represent numbers, which the sort function unfortunately does as default. Strings are sorted alphabetically. The comparison function in your code just forces the strings to be evaluated as numbers.

I'd consider it very bad API design that the sort function defaults to treating the elements as strings, but it may be necessary given JavaScript's loose type system..

Answer 4

This is because for any other language, I didn't find this problem where the function didn't sort the numbers correctly.

Consider your emphasis in the above sentence: you are precisely not sorting numbers. You are sorting strings! And JavaScript behaves like any other language would in this case.

If you want to consider these strings as numbers for the purpose of sorting, you have to tell the function this.

Answer 5

Javascript's sort sorts by default lexicographical, alphabetical. Thus as I understand it every element is treated as a string. The internal sorting algorithm is most probably quicksort or mergesort. To be able to use quicksort you need to be able to relate elements to each other, is a bigger than b? In the string case this ordering is already implemented.

Since you might want to sort your custom datatypes etc. you can provide a functional defining how to order two elements.

From your example your functional determines the order of two numbers a and b. Javascript sort then uses your function telling sort how to order the elements.

Turns out that mergesort is used by Mozilla, look at: http://stackoverflow.com/questions/234683/javascript-array-sort-implementation

Answer 6

The function sort will sort your array in an alphabetical sort order, even if it consists of integers; that's the reason why your array is sorted like that by calling sort without a parameter.

sortOrder is a comparison function that is used to define a new sort order for the array; this function will return

• 0, if a and b are of the same value
• a value > 0, if a has a bigger value than b
• a value < 0, if a has a smaller value than b

In JavaScript, "1" - "2" will return -1, which is a number, and not a string anymore; by using the comparison function sortOrder on your array consisting of numbers wrapped in strings, you're ordering the array in a numerical sort order, thus resulting in 1,5,10,25,40,100, and not in 1,10,100,25,40,5

Answer 7

You can delegate the sorting to your own sort function:

function sortnum(a,b) {
 return parseInt(a,10)-parseInt(b,10);
}
var n = ["10", "5", "40", "25", "100", "1"];
alert(n.sort(sortnum)); //=>["1", "5", "10", "25", "40", "100"]