For my new project on World of Raids I have to implement a table sorting. The browser not stable sorting and the faster sorting trick add difficulty to the task.

String Comparison

As mentionned in the Speed Up Javascript Sort() article, using a string as a key to represent each element is faster than using a custom sort function in most browsers.

Tables are commonly made of two data types: Numbers and Strings. Strings are the final representation so no work is involved there so our work will be focused on Numbers. What we want is to fit a number into a string. A string is a succession of characters, each one able to hold 256 values. So, we can see the problem as encoding the number into a base 256 which is trivial.

Padding

String comparison does not work exactly like we want it. It reads all the characters one by one and if they mismatch then it returns who is the highest. So for example "10" < "5" because '1' < '5'. We have to pad every numbers with 0 at the beginning and become "10" > "05".

In this case we are adding one 0 because 10 is 2 digits and 5 is only one. We won't know the values of other elements when making a comparison, so two solutions apply: either we iterate over all the elements and retrieve the highest, or we set an arbitrary maximum.

Characters Maximum
1 256
2 65 536
3 16 777 216
4 4 294 967 296

With that table in mind, it is obvious that it would be a waste of time to inspect every element just to find the highest value. 1 or 2 characters will probably fit most uses but if you want to be safe, you will always be able to store your number into 4 characters which is acceptable.

Here is the code to do the conversion:

function compareAsc(num, digits) {
  var s = "";
  // Encode num in base 256
  while (num !== 0) {
    s = String.fromCharCode((num % 256) | 0) + s;
    num = (num / 256) | 0;
    digits -= 1;
  }
  // Fill with 0
  while (digits > 0) {
    s = String.fromCharCode(0) + s;
    digits -= 1;
  }
  return s;
}

For the sake of simplicity, this code is using string concatenation which requires to build up new strings and make copy several times. Since this is for small strings (up to 4 characters!) this is probably alright but one looking for performances could bench this with the use of an Array with a .concat() at the end to build the string.

Also note that numbers are stored as float in Javascript, so we are rounding (flooring to be exact) all the values using the |0 trick.

Descending Order

We have made the code for an ascending sort but we have to handle the other case. We cannot just revert the order of the sorting or adding a minus sign before the number. What we have to do is to do a 256-complement of the final result, in other terms: digit = 255 - digit. Let see an example for a base 10.

00 -> 99
01 -> 98
...
54 -> 45
55 -> 44
56 -> 43
...
98 -> 01
99 -> 00

You can see that all the numbers are now sorted in the opposite order.

Here is the associated code :

function compareDesc(num, digits) {
  var s = "";
  // Encode num in base 256 and do the 256-complement
  while (num !== 0) {
    s = String.fromCharCode(255 - (num % 256) | 0) + s;
    num = (num / 256) | 0;
    digits -= 1;
  }
  while (digits >= 0) {
    s = String.fromCharCode(255) + s;
    digits -= 1;
  }
  return s;
}

Floats and Negatives

We have handled all the positive integers but they are not alone. In order to deal with the negative numbers you can apply the 2-complement to the number. This is how it is done in computer arithmetic.

To handle floats, it is possible to treat them as integers by multiplying by 10^(number of decimal displayed). So 12.34 is translated to 1234 and 11 to 1100 and it's working just fine. You will probably need more than 4 characters if you are using huge numbers though.

Stable Sorting

Implementing a table sorting requires the sorting algorithm to be stable (values that have the same key keep their original order). This property allows people to sort by multiple columns, the last one having the highest weight.

However, browser implementations of the Array.sort() are not stable. From there we have two solutions, implementing a stable sort in javascript or find a way to emulate that behaviour. Since Javascript is slow in many browsers, implementing such a computation heavy algorithm in Javascript is going to slow down things and requires more efforts than I am willing to spend on this project.

The solution instead is to understand what the stable property means and find a way to code it.

Stable sorting algorithms maintain the relative order of records with equal keys. [...] Whenever there are two records (let's say R and S) with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

We can easily transpose that sentence into the sorting function:

if (R.key == S.key)
  return compare(R.position, S.position)

We need to know one more thing to do the computation: the position of each element in the list before sorting. This is straightforward to do, you have to iterate over all the elements and update their position field. This requires n steps which is acceptable.

Here is the full Javascript code

var sort = function (a, b) {
  if (a.key === b.key)
    return a.position - b.position;
  if (a.key < b.key)
    return -1;
  return 1;
};

String comparison

To apply this concept to the string comparison, you can append the position at the end of the string. "Key" now being "Key1", "Key2" and so on. When the keys are equal, the position is used for the comparison instead. We can reuse the compareAsc() function to encode the position using the minimal size.

This works well for fixed-size strings like the representation of numbers. However common strings do not share that property and a problem arise when two strings share a common base.

Take "Method" and "Methodology". It is obvious that "Method" < "Methodology". Now append the position: "Method" + chr(250) > "Methodology" + chr(251) the comparison changed because chr(250) > 'o'. (Where chr = String.fromCharCode').

The way to fix this problem is to add a chr(0) before the position. Considering that a normal string never contains a chr(0), the chr(0) will always be lesser than any character of the string and therefore stop the comparison. The longer string always wins!

If you liked this article, you might be interested in my Twitter feed as well.
 
  • lukas

    I think this is overkill. In addition it requires extra work on both ends.
    Should you care for size you can always let your http server gzip the stream.

  • http://vjeux.com vjeux

    The main objective of this article is to benefit from the huge speedup (up to x10) of the fast sorting technique I describe in another article: http://blog.vjeux.com/2009/javascript/speed-up-javascript-sort.html

    This is indeed overkill for small arrays but if you have to sort a large number of data in the browser, this is unfortunately required!

    For the guild recruitment website it took nearly 20 seconds to sort 20000 guilds in IE7, about 1 second with this 🙂

  • correction

    You multiplied by 356 instead of 256 between 2 and 3 characters. It should be:

    Characters	Maximum
    	1	256
    	2	65 536
    	3	16 777 216
    	4	4 294 967 296
    
    
    
  • http://vjeux.com vjeux

    Indeed, that's 4 billion and not 5 billion.

    Thanks 🙂

  • Sam

    Hey mate.

    Is there a way to display some sort of example of this?

    I know this post is ancient, but many posts from stackoverflow and google search results pointed me here.

    My problem is that i'm creating a table with a jquery plugin that reads from a json object, this object is created server-side by a query to the DB, usually, the table is around 700 rows and the "rendering" process of the table is done in a jiffy, but when it comes to sort the data, well... the browser has died on me many times.

    I've tried to implement several sorting algorithms, but they all seem to be very complex and overkill and sometimes they just don't seem to work at all.

    Lately i've been using the good old Array.sort() and Array.reverse() but this implementation is not an option anymore.

    Also, with the use of the application, the data has increased in size and complexity, it's very common for the table to display around 5 thousand rows from a single call.

    I'm considering to put the sorting function on the server side but as a last resort i was trying to implement this algorithm but i've failed miserabily all day long.

    If you could help me it would be awesome or if you could explain me the logic behind the sorting algorithm ( in general ) maybe i could come up with a more suitable approach for my scenario.

    Many thanks and keep up the good work mate.

  • Pingback: Stable Sorting in JavaScript… | Adam's Big Data Discoveries()

  • everlasto

    What about break and return if str1.length > str2.length?

  • Pingback: 快速稳定排序算法在JavaScript中的实现 – CodingBlog()

 

Related Posts

  • August 10, 2009 Speed Up Javascript Sort() (1)
    By overriding the toString Object prototype, it is possible to speed up by 5x the sort function. This is an easy to implement trick that gives astonishing results I wanted to know if there were ways to speed up the Javascript Sort function. I came across an interesting article (Yet […]
  • December 24, 2009 Guild Recruitement – Search Optimizations (0)
    In World of Raids Guild Recruitment Tool, we wanted the search to be instant! We achieved this goal by not having a single page refresh or ajax call while updating the settings. Since it runs in the browser, performance was a real concern. We will see in this article what were the tricks […]
  • October 30, 2009 Javascript – Dynamic Query Throttling (2)
    Working on the World of Raids Recruitment Tool we wanted automatic saving while editing. There are basically two ways of handling the problem. Send update everytime something changes. The main advantage of this technique is that you are always up to date. However, it is spamming the […]
  • August 4, 2009 Project – MMO-Champion Optimization (0)
    MMO-Champion is the biggest news website of World of Warcraft. The main page is viewed millions times a month and was done with old school tables. As a result, it was really slow to load but worse, all the content had to be loaded before being displayed. The first thing I did was […]
  • October 8, 2011 Find HTMLEntity for any Character (4)
    I've always be annoyed when I want to use a character such as » in HTML as I struggle to find the corresponding HTML Entity. This is why I made this small utility. Just paste the sexy UTF-8 character you found and it will give you the associated HTML-ready code :) Enter any weird […]