sorting javascript gets hang

Question

Hi ,

I am rendering around 3000 records,

i am using this sorting open source script ,

When i click the column, my browser getting hang very shortly ,

i cant able to continue,

Is there any solution for this prob.

link text

Answer 1

You have answered your own question in a way.

Take a look at the sorting script.

Sorting 3000 records, rearranging the DOM and rendering the output.

It will for sure take time.

This script you are using is meant for small sets of records.

Suggestion: Using server side sorting and render the results in pages, each page containing say 50 records. For about 3000 records, you will have around 60 pages.

Lets say you are on the 45th page. Then you fire a SQL query to sort (asc/desc) and skip the first 44*50 records and retrieve the next 50 records (for 45th page).

Answer 2

This library seems to use DOM manipulations to sort.

It would be better to generate the table each time and inject it using innerHTML.
In today's javascript engines this looks instantaneous.

Even IE6 is good at that.

That being said... showing 3000 lines to a human is something questionable.
But this is another debate ;)

Answer 3

Update 2

I sent my updates to the original author of the above code, but until he decides to post it, here is my updated version. It speeds up the use of the standard built-in sort() if you decide to do that. It also replaces the stable cocktail sort with a stable merge sort. The merge sort is nearly as fast as using sort() in my tests. I hope that helps.

Update

I no longer think that there is a great discrepancy between browsers as far as the built-in sort() function is concerned. While IE8, for instance, is much slower overall than say Chrome, I don't think that it has to do with just the sorting function. I did some profiling in IE8 using some random data. I found that the original code can be improved quite substantially when the column data is numeric or a date. Putting the regexp searches in the comparison functions for these data types slows things down a lot because they are being every time a comparison is done between elements which for 3000 elements is around 60,000 comparisons. The number of regexp's is twice that. By doing all of this before we start sorting, we do 3,000 regexp's rather than 120,000. This can be about a 50% savings in time. I'll submit my changes to the sorttable code in a little bit.

Other than that, most of the time is reordering the DOM elements around, not sorting (unless you are using the shaker sort). If you can find a faster way to do that then you can save some time there, but I don't know of any way to do that.

Original answer:

The problem here may have to do with the actual sort. If you uncommented some of the code there (and commented out some other code), then your code is using a shaker sort to get a stable sort. Shaker sort is essentially a bidirectional bubble sort. Bubble sorts are very slow, O(N^2). If you didn't uncomment that code, then it is using javascript's built-in sort() function with various comparator functions. The problem with this is that this sort() function is implemented differently in different browsers so you might want to see if this problem happens in some browsers and not in others. Apparently, the Webkit code still uses a selection, or min, sort which is O(N^2). That almost makes me want to cry. What browser have you been using to test this?

If the sort function turns out to be the problem, then you might try changing the above code to sue a merge sort or quicksort which are both O(N log N). Quicksorts are a little bit more tricky to avoid O(N^2) cases so you might want to stick with merge sort. Also, merge sort is a stable sort. This page has an example to get you started with merge sort.