# Fast stable sorting algorithm implementation in javascript

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!

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

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

http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

The code can be found at the above website:

``````function mergeSort(arr)
{
if (arr.length < 2)
return arr;

var middle = parseInt(arr.length / 2);
var left   = arr.slice(0, middle);
var right  = arr.slice(middle, arr.length);

return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
var result = [];

while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());

return result;
}
``````

EDIT:

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

I know that this question has been answered for some time, but I happen to have a good stable merge sort implementation for Array and jQuery in my clipboard, so I'll share it in the hopes that some future searchers might find it useful.

It allows you to specify your own comparison function just like the normal `Array.sort` implementation.

## Implementation

``````// Add stable merge sort to Array and jQuery prototypes
// Note: We wrap it in a closure so it doesn't pollute the global
//       namespace, but we don't put it in \$(document).ready, since it's
//       not dependent on the DOM
(function() {

// expose to Array and jQuery
Array.prototype.mergeSort = jQuery.fn.mergeSort = mergeSort;

function mergeSort(compare) {

var length = this.length,
middle = Math.floor(length / 2);

if (!compare) {
compare = function(left, right) {
if (left < right)
return -1;
if (left == right)
return 0;
else
return 1;
};
}

if (length < 2)
return this;

return merge(
this.slice(0, middle).mergeSort(compare),
this.slice(middle, length).mergeSort(compare),
compare
);
}

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;
}
})();
``````

## Example Usage

``````var sorted = [
'Finger',
'Sandwich',
'sandwich',
'5 pork rinds',
'a guy named Steve',
'some noodles',
'mops and brooms',
'Potato Chip Brand® chips'
].mergeSort(function(left, right) {
lval = left.toLowerCase();
rval = right.toLowerCase();

console.log(lval, rval);
if (lval < rval)
return -1;
else if (lval == rval)
return 0;
else
return 1;
});

sorted == ["5 pork rinds", "a guy named Steve", "Finger", "mops and brooms", "Potato Chip Brand® chips", "Sandwich", "sandwich", "some noodles"];
``````

Somewhat shorter version of the same thing using ES2017 features like arrow functions and destructuring:

# Function

``````var stableSort = (arr, compare) => arr
.map((item, index) => ({item, index}))
.sort((a, b) => compare(a.item, b.item) || a.index - b.index)
.map(({item}) => item)
``````

It accepts input array and compare function:

``````stableSort([5,6,3,2,1], (a, b) => a - b)
``````

It also returns new array instead of making in-place sort like the built-in Array.sort() function.

# Test

If we take the following `input` array, initially sorted by `weight`:

``````// sorted by weight
var input = [
{ height: 100, weight: 80 },
{ height: 90, weight: 90 },
{ height: 70, weight: 95 },
{ height: 100, weight: 100 },
{ height: 80, weight: 110 },
{ height: 110, weight: 115 },
{ height: 100, weight: 120 },
{ height: 70, weight: 125 },
{ height: 70, weight: 130 },
{ height: 100, weight: 135 },
{ height: 75, weight: 140 },
{ height: 70, weight: 140 }
]
``````

Then sort it by `height` using `stableSort`:

``````stableSort(input, (a, b) => a.height - b.height)
``````

Results in:

``````// Items with the same height are still sorted by weight
// which means they preserved their relative order.
var stable = [
{ height: 70, weight: 95 },
{ height: 70, weight: 125 },
{ height: 70, weight: 130 },
{ height: 70, weight: 140 },
{ height: 75, weight: 140 },
{ height: 80, weight: 110 },
{ height: 90, weight: 90 },
{ height: 100, weight: 80 },
{ height: 100, weight: 100 },
{ height: 100, weight: 120 },
{ height: 100, weight: 135 },
{ height: 110, weight: 115 }
]
``````

However sorting the same `input` array using the built-in `Array.sort()` (in Chrome/NodeJS):

``````input.sort((a, b) => a.height - b.height)
``````

Returns:

``````var unstable = [
{ height: 70, weight: 140 },
{ height: 70, weight: 95 },
{ height: 70, weight: 125 },
{ height: 70, weight: 130 },
{ height: 75, weight: 140 },
{ height: 80, weight: 110 },
{ height: 90, weight: 90 },
{ height: 100, weight: 100 },
{ height: 100, weight: 80 },
{ height: 100, weight: 135 },
{ height: 100, weight: 120 },
{ height: 110, weight: 115 }
]
``````

# Update

`Array.prototype.sort` is now stable in V8 v7.0 / Chrome 70!

Previously, V8 used an unstable QuickSort for arrays with more than 10 elements. Now, we use the stable TimSort algorithm.

source

The following sorts the supplied array, by applying the supplied compare function, returning the original index comparison when the compare function returns 0:

``````function stableSort(arr, compare) {
var original = arr.slice(0);

arr.sort(function(a, b){
var result = compare(a, b);
return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
});

return arr;
}
``````

The example below sorts an array of names by surname, retaining the order of equal surnames:

``````var names = [
{ surname: "Williams", firstname: "Mary" },
{ surname: "Doe", firstname: "Mary" },
{ surname: "Johnson", firstname: "Alan" },
{ surname: "Doe", firstname: "John" },
{ surname: "White", firstname: "John" },
{ surname: "Doe", firstname: "Sam" }
]

function stableSort(arr, compare) {
var original = arr.slice(0);

arr.sort(function(a, b){
var result = compare(a, b);
return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
});

return arr;
}

stableSort(names, function(a, b) {
return a.surname > b.surname ? 1 : a.surname < b.surname ? -1 : 0;
})

names.forEach(function(name) {
console.log(name.surname + ', ' + name.firstname);
});``````

Here's a stable implementation. It works by using the native sort, but in cases where elements compare as equal, you break ties using the original index position.

``````function stableSort(arr, cmpFunc) {
//wrap the arr elements in wrapper objects, so we can associate them with their origional starting index position
var arrOfWrapper = arr.map(function(elem, idx){
return {elem: elem, idx: idx};
});

//sort the wrappers, breaking sorting ties by using their elements orig index position
arrOfWrapper.sort(function(wrapperA, wrapperB){
var cmpDiff = cmpFunc(wrapperA.elem, wrapperB.elem);
return cmpDiff === 0
? wrapperA.idx - wrapperB.idx
: cmpDiff;
});

//unwrap and return the elements
return arrOfWrapper.map(function(wrapper){
return wrapper.elem;
});
}
``````

a non-thorough test

``````var res = stableSort([{a:1, b:4}, {a:1, b:5}], function(a, b){
return a.a - b.a;
});
console.log(res);
``````

another answer alluded to this, but didn't post teh codez.

but, its not fast according to my benchmark. I modified a merge sort impl to accept a custom comparator function, and it was much faster.

You can also use Timsort. This is a really complicated algorithm (400+ lines, hence no source code here), so see Wikipedia's description or use one of the existing JavaScript implementations:

GPL 3 implementation. Packaged as Array.prototype.timsort. Appears to be an exact rewrite of Java code.

Public domain implementation Meant as a tutorial, the sample code only shows its use with integers.

Timsort is a highly optimized hybrid of mergesort and shuffle sort and is the default sorting algorithm in Python and in Java (1.7+). It is a complicated algorithm, since it uses different algorithms for many special cases. But as a result it's extremely fast under a wide variety of circumstances.

A simple one mergeSort from http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

``````var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];

function mergeSort(arr)
{
if (arr.length < 2)
return arr;

var middle = parseInt(arr.length / 2);
var left   = arr.slice(0, middle);
var right  = arr.slice(middle, arr.length);

return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
var result = [];

while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());

return result;
}

console.log(mergeSort(a));
``````

I have to sort multidimensional arrays by an arbitrary column, and then by another. I use this function to sort:

``````function sortMDArrayByColumn(ary, sortColumn){

//Adds a sequential number to each row of the array
//This is the part that adds stability to the sort
for(var x=0; x<ary.length; x++){ary[x].index = x;}

ary.sort(function(a,b){
if(a[sortColumn]>b[sortColumn]){return 1;}
if(a[sortColumn]<b[sortColumn]){return -1;}
if(a.index>b.index){
return 1;
}
return -1;
});
}
``````

Notice that ary.sort never returns zero, which is where some implementations of the "sort" function make decisions that might not be right.

This is pretty darn fast, too.

Here's how you could extend JS default Array object with a prototype method utilizing MERGE SORT. This method allows for sorting on a specific key (first parameter) and a given order ('asc'/'desc' as second parameter)

``````Array.prototype.mergeSort = function(sortKey, direction){
var unsortedArray = this;
if(unsortedArray.length < 2) return unsortedArray;

var middle = Math.floor(unsortedArray.length/2);
var leftSubArray = unsortedArray.slice(0,middle).mergeSort(sortKey, direction);
var rightSubArray = unsortedArray.slice(middle).mergeSort(sortKey, direction);

var sortedArray = merge(leftSubArray, rightSubArray);
return sortedArray;

function merge(left, right) {
var combined = [];
while(left.length>0 && right.length>0){
var leftValue = (sortKey ? left[0][sortKey] : left[0]);
var rightValue = (sortKey ? right[0][sortKey] : right[0]);
combined.push((direction === 'desc' ? leftValue > rightValue : leftValue < rightValue) ? left.shift() : right.shift())
}
return combined.concat(left.length ? left : right)
}
}``````

You can test this out yourself by dropping the above snippet into your browser console, then trying:

``````var x = [2,76,23,545,67,-9,12];
x.mergeSort(); //[-9, 2, 12, 23, 67, 76, 545]
x.mergeSort(undefined, 'desc'); //[545, 76, 67, 23, 12, 2, -9]
``````

Or order based on a specific field in an array of objects:

``````var y = [
{startTime: 100, value: 'cat'},
{startTime: 5, value: 'dog'},
{startTime: 23, value: 'fish'},
{startTime: 288, value: 'pikachu'}
]
y.mergeSort('startTime');
y.mergeSort('startTime', 'desc');
``````

So I needed a stable sort for my React+Redux app, and Vjeux's answer here helped me. However, my (generic) solution seems different than the others I see here so far, so I'm sharing it in case anyone else has a matching use-case:

• I really just want to have something similar to the `sort()` API, where I can pass a comparator function.
• Sometimes I can sort in-place, and sometimes my data is immutable (because Redux) and I need a sorted copy instead. So I need a stable sorting function for each use-case.
• ES2015.

My solution is to create a typed array of `indices`, then use a comparison function to sort these indices based on the to-be-sorted array. Then we can use the sorted `indices` to either sort the original array or create a sorted copy in a single pass. If that's confusing, think of it this way: where you would normally pass a comparison function like:

``````(a, b) => {
/* some way to compare a and b, returning -1, 0, or 1 */
};
``````

``````(i, j) => {
let a = arrayToBeSorted[i], b = arrayToBeSorted[j];
/* some way to compare a and b, returning -1 or 1 */
return i - j; // fallback when a == b
}
``````

Speed is good; it is basically the built-in sorting algorithm is, plus two linear passes in the end, and one extra layer of pointer indirection overhead.

Happy to receive feedback on this approach. Here is my full implementation of it it:

``````/**
* - `array`: array to be sorted
* - `comparator`: closure that expects indices `i` and `j`, and then
*   compares `array[i]` to `array[j]` in some way. To force stability,
*   end with `i - j` as the last "comparison".
*
* Example:
* ```
*  let array = [{n: 1, s: "b"}, {n: 1, s: "a"}, {n:0, s: "a"}];
*  const comparator = (i, j) => {
*    const ni = array[i].n, nj = array[j].n;
*    return ni < nj ? -1 :
*      ni > nj ? 1 :
*        i - j;
*  };
*  stableSortInPlace(array, comparator);
*  // ==> [{n:0, s: "a"}, {n:1, s: "b"}, {n:1, s: "a"}]
* ```
*/
function stableSortInPlace(array, comparator) {
return sortFromIndices(array, findIndices(array, comparator));
}

function stableSortedCopy(array, comparator){
let indices = findIndices(array, comparator);
let sortedArray = [];
for (let i = 0; i < array.length; i++){
sortedArray.push(array[indices[i]]);
}
return sortedArray;
}

function findIndices(array, comparator){
// Assumes we don't have to worry about sorting more than
// 4 billion elements; if you know the upper bounds of your
// input you could replace it with a smaller typed array
let indices = new Uint32Array(array.length);
for (let i = 0; i < indices.length; i++) {
indices[i] = i;
}
// after sorting, `indices[i]` gives the index from where
// `array[i]` should take the value from, so to sort
// move the value at at `array[indices[i]]` to `array[i]`
return indices.sort(comparator);
}

// If I'm not mistaken this is O(2n) - each value is moved
// only once (not counting the vacancy temporaries), and
// we also walk through the whole array once more to check
// for each cycle.
function sortFromIndices(array, indices) {
// there might be multiple cycles, so we must
// walk through the whole array to check.
for (let k = 0; k < array.length; k++) {
// advance until we find a value in
// the "wrong" position
if (k !== indices[k]) {
// create vacancy to use "half-swaps" trick,
// props to Andrei Alexandrescu
let v0 = array[k];
let i = k;
let j = indices[k];
while (j !== k) {
// half-swap next value
array[i] = array[j];
// array[i] now contains the value it should have,
// so we update indices[i] to reflect this
indices[i] = i;
// go to next index
i = j;
j = indices[j];
}
// put original array[k] back in
// and update indices
array[i] = v0;
indices[i] = i;
}
}
return array;
}
``````

I know this has been plenty answered. I just wanted to go ahead an post a quick TS implementation for anyone that landed here looking for that.

``````export function stableSort<T>( array: T[], compareFn: ( a: T, b: T ) => number ): T[] {
const indices = array.map( ( x: T, i: number ) => ( { element: x, index: i } ) );

return indices.sort( ( a, b ) => {
const order = compareFn( a.element, b.element );
return order === 0 ? a.index - b.index : order;
} ).map( x => x.element );
}
``````

The method does no longer run in-place, as the native sort does. I also want to point out that it is not the most efficient. It adds two loops of the order O(n). though sort itself is most likely O(n log(n)) so it's less than that.

Some of the solutions mentioned are more performant, thought this might be less code, also using internal `Array.prototype.sort`.

(For a Javascript solution, just remove all the types)

Counting Sort is faster than merge sort (it performs in O(n) time) and it is intended for use on integers.

``````Math.counting_sort = function (m) {
var i
var j
var k
var step
var start
var Output
var hash
k = m.length
Output = new Array ()
hash = new Array ()
// start at lowest possible value of m
start = 0
step = 1
// hash all values
i = 0
while ( i < k ) {
var _m = m[i]
hash [_m] = _m
i = i + 1
}
i = 0
j = start
// find all elements within x
while ( i < k ) {
while ( j != hash[j] ) {
j = j + step
}
Output [i] = j
i = i + 1
j = j + step
}
return Output
}
``````

Example:

``````var uArray = new Array ()<br/>
var sArray = new Array ()<br/><br/>
uArray = [ 10,1,9,2,8,3,7,4,6,5 ]<br/>
sArray = Math.counting_sort ( uArray ) // returns a sorted array
``````

You can use the following polyfill to implement a stable sort regardless of the native implementation, based on the assertion made in this answer:

``````// ECMAScript 5 polyfill
Object.defineProperty(Array.prototype, 'stableSort', {
configurable: true,
writable: true,
value: function stableSort (compareFunction) {
'use strict'

var length = this.length
var entries = Array(length)
var index

// wrap values with initial indices
for (index = 0; index < length; index++) {
entries[index] = [index, this[index]]
}

// sort with fallback based on initial indices
entries.sort(function (a, b) {
var comparison = Number(this(a[1], b[1]))
return comparison || a[0] - b[0]
}.bind(compareFunction))

// re-map original array to stable sorted values
for (index = 0; index < length; index++) {
this[index] = entries[index][1]
}

return this
}
})

// usage
const array = Array(500000).fill().map(() => Number(Math.random().toFixed(4)))

const alwaysEqual = () => 0
const isUnmoved = (value, index) => value === array[index]

// not guaranteed to be stable
console.log('sort() stable?', array
.slice()
.sort(alwaysEqual)
.every(isUnmoved)
)
// guaranteed to be stable
console.log('stableSort() stable?', array
.slice()
.stableSort(alwaysEqual)
.every(isUnmoved)
)

// performance using realistic scenario with unsorted big data
function time(arrayCopy, algorithm, compare) {
var start
var stop

start = performance.now()
algorithm.call(arrayCopy, compare)
stop = performance.now()

return stop - start
}

const ascending = (a, b) => a - b

const msSort = time(array.slice(), Array.prototype.sort, ascending)
const msStableSort = time(array.slice(), Array.prototype.stableSort, ascending)

console.log('sort()', msSort.toFixed(3), 'ms')
console.log('stableSort()', msStableSort.toFixed(3), 'ms')
console.log('sort() / stableSort()', (100 * msSort / msStableSort).toFixed(3) + '%')``````

Running the performance tests implemented above, `stableSort()` appears to run at about 57% of the speed of `sort()` on Chrome version 59-61.

Using `.bind(compareFunction)` on the wrapped anonymous function within `stableSort()` boosted that relative performance from about 38% by avoiding an unneeded scoped reference to `compareFunction` on each call by assigning it to the context instead.

### Update

Changed ternary operator to logical short-circuiting, which tends to perform better on average (appears to make a 2-3% difference in efficiency).

According to the v8 dev blog and caniuse.com `Array.sort` is already stable as required by the spec in modern browsers, so you don't need to roll your own solution. The only exception I can see is Edge, which should soon move over to chromium and support it as well.

``````function sort(data){
var result=[];
var array = data;
const array2=data;
const len=array2.length;
for(var i=0;i<=len-1;i++){
var min = Math.min.apply(Math,array)
result.push(min);
var index=array.indexOf(min)
array.splice(index,1);
}
return result;
}
sort([9,8,5,7,9,3,9,243,4,5,6,3,4,2,4,7,4,9,55,66,33,66]);``````