Some browsers’ JavaScript implementations don’t implement a stable sort,
but stable sorting can be so handy if you want to, say, sort a table by
multiple columns. So here’s a quick and easy way to add an efficient, stable
merge sort to the Array prototype. Note that this even lets you define
your own comparison function, just like JavaScript’s own Array.sort
function!
Bonus!
We’ll also add this sorting function to jQuery, which already applies
Array.sort for $.sort and $(selection).sort.
Implementation
/*!
* Merge Sort in JavaScript v1.0
* http://github.com/justinforce/merge-sort
*
* Copyright (c) 2011, Justin Force
* Licensed under the BSD 3-Clause License
*/
/*jslint browser: true, indent: 2 */
/*global jQuery */
(function () {
'use strict';
// Add stable merge sort method to Array prototype
if (!Array.mergeSort) {
Array.prototype.mergeSort = function (compare) {
var length = this.length,
middle = Math.floor(length / 2);
// define default comparison function if none is defined
if (!compare) {
compare = function (left, right) {
if (left < right) {
return -1;
} else if (left === right) {
return 0;
} else {
return 1;
}
};
}
if (length < 2) {
return this;
}
function merge(left, right, compare) {
var result = [];
while (left.length > 0 || right.length > 0) {
if (left.length > 0 && right.length > 0) {
if (compare(left[0], right[0]) <= 0) {
result.push(left[0]);
left = left.slice(1);
} else {
result.push(right[0]);
right = right.slice(1);
}
} else if (left.length > 0) {
result.push(left[0]);
left = left.slice(1);
} else if (right.length > 0) {
result.push(right[0]);
right = right.slice(1);
}
}
return result;
}
return merge(
this.slice(0, middle).mergeSort(compare),
this.slice(middle, length).mergeSort(compare),
compare
);
};
}
// Add merge sort to jQuery if it's present
if (window.jQuery !== undefined) {
jQuery.fn.mergeSort = function (compare) {
return jQuery(Array.prototype.mergeSort.call(this, compare));
};
jQuery.mergeSort = function (array, compare) {
return Array.prototype.mergeSort.call(array, compare);
};
}
}());
Examples
Arrays
I have some arrays of numbers, strings, and miscellany that need sorting.
var numbers = [4, 2, 2, 43, 98, 29, 0, 4.3, 9.23],
strings = ['Porcupine', 'dolphin', 'Squirrel', 'penguin', 'Lion'],
miscellany = ['23', 89, 'stapler', 4];
To sort my numbers, I would just
numbers.mergeSort();
// [0, 2, 2, 4, 4.3, 9.23, 29, 43, 98]
To sort my strings, I can also just
strings.mergeSort();
// ["Lion", "Porcupine", "Squirrel", "dolphin", "penguin"]
But with the default comparison, they don’t come out alphabetical. The
capitalized words come first. For a case insensitive sort, I need to define a
compare function.
strings.mergeSort(function (left, right) {
left = left.toLowerCase();
right = right.toLowerCase();
if (left < right) {
return -1;
} else if (left === right) {
return 0;
} else {
return 1;
}
});
// ["dolphin", "Lion", "penguin", "Porcupine", "Squirrel"]
That’s more like it. How about that last list of miscellany? I want my numbers
first, then my words, but I want strings containing numbers treated as numbers.
Pretty specific, but I can describe it with a function.
miscellany.mergeSort(function (left, right) {
if (isNaN(left) === false) {
left = parseFloat(left);
}
if (isNaN(right) === false) {
right = parseFloat(right);
}
if (typeof left !== typeof right) {
if (typeof left === 'number') {
return -1;
} else {
return 1;
}
} else {
if (left < right) {
return -1;
} else if (left === right) {
return 0;
} else {
return 1;
}
}
});
// [4, "23", 89, "stapler"]
jQuery
Used with jQuery, you’ll probably always want to supply a compare function, so
I’ll only discuss those cases. Here’s a non-trivial example. I have a table:
<table id=demo>
<thead>
<tr>
<th>First Name
<th>Last Name
<th>Occupation
<tbody>
<tr>
<td>Bob
<td>Durp
<td>Programmer
<tr>
<td>Alice
<td>Morp
<td>Programmer
<tr>
<td>Luis
<td>Durp
<td>Analyst
</table>
Which looks something like
| First Name
| Last Name
| Occupation
|
| Bob
| Durp
| Programmer
|
| Alice
| Morp
| Programmer
|
| Luis
| Durp
| Analyst
|
I can sort by any column. To sort by Last Name (the 2nd column):
$('#demo tbody').html($('#demo tbody tr').mergeSort(function (left, right) {
left = $(left).find('td:nth-child(2)').text().toLowerCase();
right = $(right).find('td:nth-child(2)').text().toLowerCase();
if (left < right) {
return -1;
} else if (left === right) {
return 0;
} else {
return 1;
}
}));
And the table will be updated to look like this:
| First Name
| Last Name
| Occupation
|
| Bob
| Durp
| Programmer
|
| Luis
| Durp
| Analyst
|
| Alice
| Morp
| Programmer
|
You can see how with a little imagination and the application of a click
handler, this could be extrapolated to allow real-time resorting of a table.
And since it’s a stable sort, you can sort by multiple columns sequentially.
Other
You can apply this merge sort to any other compatible type in the same way (see
list in the Syntax section above for compatibility).
$.mergeSort(aListOfSomeKind, compareMyListItems);
The $.mergeSort() syntax is just sugar for
Array.prototype.mergeSort.call(), so the above is equivalent to
Array.prototype.mergeSort.call(aListOfSomeKind, compareMyListItems);
But just use the simpler $.mergeSort() syntax. :)
GitHub
The project, like most of my work, lives at GitHub. For complete documentation,
forking, and keeping up with the latest version, check out merge-sort.js on
GitHub.