Fast stable sorting algorithm implementation in javascript

Question

I'm looking to sort an array of about 200-300 objects, sorting on a specific key and a given order (asc/desc). The order of results must be consistent and stable.

What would be the best algorithm to use, and could you provide an example of it's implementation in javascript?

Thanks!

Answer 1

Since you are looking for something stable, the merge sort should do.

http://en.literateprograms.org/Merge_sort_(JavaScript)

EDIT:

According to this post, it looks like Array.Sort in some implementations uses a merge sort.

Answer 2

Will the built in sort function do? http://www.w3schools.com/jsref/jsref%5Fsort.asp

Answer 3

Check this article:

http://www.hedgerwow.com/360/dhtml/js%5Farray%5Fstable%5Fsort.html

It seems that only FF 2.0 and Opera 9 and earlier have a non-stable sort implementation. All other mainstream browsers do.

Answer 4

You should be able to utilize the core Array.sort method. Example...

var data = []; //populate array

function sortByName(a, b) {
  var x = a.LastName.toLowerCase();
  var y = b.LastName.toLowerCase();
  return ((x < y) ? -1 : ((x > y) ? 1 : 0));
}

data.sort(sortByName);

Note: this only sorts ascending. But you can take care of that by tweaking the function or using Array.reverse.

Answer 5

It is possible to get a stable sorting from a non-stable sort function.

Before sorting you get the position of all the elements. In your sort condition, if both elements are equal, then you sort by the position.

Tada! You've got a stable sort.

I've written an article about it on my blog if you want to know more about this technique and how to implement it: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html