kostik | Yet another faster JavaScript sorting (Reply)

It is no secret that the demand on applications with “AJAX” in the name is continually increasing. Nolens volens one has to do some things with unadapted to them tools: an illustration in point is Internet Explorer — a program which is unadapted to execution of the code that would be standardized and had a common sense. Recently I had to deal with one of its problems. I had to sort out an array of objects by the given field. IE did it 100 times slower than FireFox! Solution allows sorting out six times faster than Internet Explorer. A link to the library implementing this method follows.

Problem

With trivial code

// Array а contains 15000 elements
a.sort(function(a, b){return b.item — a.item;})

IE needs 40(!) seconds to think (15000 was taken as a test, a real array is certainly less). (FireFox does the same in 422ms, approximately 100 times faster!) The realization of the sorting process on the server side would require changing of a large part of the code because the user selects a field and a method of sorting; this was a problem.

Solution

After short googling I found an excellent article by Russel Lindsay: “Faster Javascript sorting”. He uses a simple trick: to rewrite the method toString() for addressing to the object’s property directly, convert numbers ([1, 2, 10] into strings ['01','02','10']) and use sort() without parameters for increasing sorting speed. Below the results of the test (with my implementation of this idea):

Internet Explorer41516ms – sort(function(a, b){return b.item - a.item;})

7031ms - sort() for the array where numbers were converted into string

7047ms – sort() and reverse() for the array where numbers were converted into stringFireFox

438ms – sort(function(a, b){return b.item - a.item;})

891ms - sort() for the array where numbers were converted into string

954ms – sort() and reverse() for the array where numbers were converted into string

Thus the trick of adding numbers with zeros to strings gives a six times quicker sorting in Internet Explorer and twice slower sorting in FF which allows using the code in both browsers.

Russel Lindsay uses the fixed size mask and the array ([1, 2, 10] turns not into [01, 02, 10] but into ['00000000001',' 00000000002',' 00000000010']). This is awful for many reasons and memory used is one of them. So I wrote a small library based on his code. It adds to Array() following methods: Array.sortIntAsc(property) and Array.sortIntDesc(property) for sorting array by integer property, Array.sortAsc(property), and Array.sortDesc(property) for sorting by string property.

Example

[js] var team = [
{name:’Bill’, age:25},
{name:’John’, age:21},
{name:’Ann’, age:20}
];

alert([team[0].name,team[1].name,team[2].name]);
// Bill, John, Ann

team.sortIntAsc(’age’);
alert([team[0].name,team[1].name,team[2].name]);
// Ann, John, Bill

team.sortAsc(’name’);
alert([team[0].name,team[1].name,team[2].name]);
// Ann, Bill, John

[/js]

My 2 cents

This method is in my humble opinion a good solution of this particular problem (thank you, Russel!). Also it is a good illustration: the best way to do something with data in the Internet Explorer is not to do anything. I mean to organize the data processing flow in such a way as to leave the data processing (including any sorting) on the server side. Otherwise when IE will deal with trivial tasks terrible you will have to spend a lot of time to find a strange detour.

download library (zip)

_{http://blog.piterpen.net/2007/01/08/yet-another-faster-javascript-sorting/}