Categories
askquestion

Fast stable sorting algorithm implementation in javascript

Fast stable sorting algorithm implementation in javascript

Ask Question

Asked
10 years, 6 months ago

Active
1 month ago

Viewed
50k times

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{
margin-bottom:0;
}

99

34

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!

javascript algorithm sorting

share|improve this question

asked Sep 15 ’09 at 14:40

William CasarinWilliam Casarin

2,24511 gold badge2121 silver badges2222 bronze badges

5

Since at least Chrome’s array sort doesn’t seem to be stable, relying on the built-in array sort is not an option for you.

– Nosredna
Sep 15 ’09 at 14:56

To summarize: I went with a hand rolled merge sort due to Array.sort stability inconsistencies between modern browsers (mainly chrome not implementing a stable sort at the time of this comment). Thanks everyone for your help!

– William Casarin
Sep 15 ’09 at 15:30

What do we mean by “stable” sort?

– mowwwalker
Dec 24 ’13 at 23:46

2

@mowwwalker Stable sort is a sort in which all of the items with the same sorting value are left in the same order as in the original collection. en.wikipedia.org/wiki/Sorting_algorithm#Stability

– Kornelije Petak
Feb 27 ’14 at 23:47

To answer “what is the best algorithm to use” we need to know if there is any underlying structure to your data. A lot of the answers below just talk about using merge sort, or quick sort, in reality it depends on the data. It’s not a simple problem to just answer i wouldn’t say. Google a few sorting algorithms and read about them to see what i mean. TimSort and Radix Sort are two good examples i’d reccomend reading about.

– will
Jun 25 ’14 at 0:04

 | 
show 2 more comments

15 Answers
15

Active

Oldest

Votes

111

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

share|improve this answer

answered Jan 18 ’10 at 10:13

VjeuxVjeux

5,48044 gold badges2828 silver badges2323 bronze badges

28

Could you please provide the answer here instead of posting and linking to your blog! Thanks

– Mohammad Kermani
Dec 11 ’16 at 7:39

4

A link to a solution is welcome, but please ensure your answer is useful without it: add context around the link so your fellow users will have some idea what it is and why it’s there, then quote the most relevant part of the page you’re linking to in case the target page is unavailable. Answers that are little more than a link may be deleted.

– Samuel Liew♦
Oct 9 ’18 at 2:50

@Vjeux since this is getting to be a popular, do you mind pasting the relevant code into this answer? It would help a lot! thanks!

– William Casarin
Jun 30 ’19 at 15:50

add a comment
 | 

33

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.

share|improve this answer

edited May 23 ’17 at 12:10

Community♦

111 silver badge

answered Sep 15 ’09 at 14:42

kemiller2002kemiller2002

103k2525 gold badges183183 silver badges237237 bronze badges

++ Merge sort is my favorite. It’s simple and stable with no bad worst cases.

– Mike Dunlavey
Sep 15 ’09 at 15:05

The link to the website is down 🙁

– ahitt6345
Feb 29 ’16 at 0:47

found a new website for the example.

– kemiller2002
Feb 29 ’16 at 9:52

6

Note: Array#shift may workn in O(n) time and so your merge in O(n*n).

– 4esn0k
Mar 14 ’16 at 4:58

add a comment
 | 

21

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 }
]

Resources

Wikipedia
MDN
JSFiddle

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

share|improve this answer

edited Sep 3 ’18 at 15:39

answered Feb 7 ’18 at 9:46

simosimo

11.3k66 gold badges3838 silver badges5151 bronze badges

1

The stableSort function is a really great solution!

– lhermann
Feb 14 at 13:15

add a comment
 | 

16

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”];

share|improve this answer

edited Mar 4 ’14 at 18:42

answered Oct 11 ’11 at 18:11

Justin ForceJustin Force

5,23933 gold badges2323 silver badges3838 bronze badges

4

Note this is at odds with the native sort, which works in place, meaning this cannot just be dropped in.

– Eric
Feb 28 ’14 at 21:31

3

Maybe stable, but this method is about 20 times slower than native array.sort, see test here for both strings and integers -> jsfiddle.net/QC64j

– davidkonrad
Mar 4 ’14 at 15:05

2

Of course it’s slower than native sort—it’s not native. That’s impossible. It’s also true that it doesn’t do an in place sort. That’s also impossible (best case you create a copy then overwrite the original). Besides, returning a sorted copy is more JavaScript-y despite JavaScript’s own native sort behavior. The function is also called mergeSort and not sort, so it’s not intended as a drop in replacement. Sometimes you just need a stable merge sort, e.g. when sorting tables by column.

– Justin Force
Mar 4 ’14 at 18:40

1

Wrong, Node’s Native sort is written in javascript. Its entirely possible for an algorithm programmed in javascript to out-speed the native sort. I built a sorting algorithm entirely in javascript(a type of adaptive merge sort) that Kremes/creams/Kreams The native quicksort in node. The point of this comment is to show that native does not matter in the case of javascript because the sorting algorithm is written in javascript and not in some higher language such as c++. Proof is here: github.com/nodejs/node/blob/master/deps/v8/src/js/array.js

– ahitt6345
Feb 29 ’16 at 0:39

2

For anyone who wants an in-place, drop-in solution that’s much faster than this implementation, check out my answer.

– Patrick Roberts
Sep 19 ’17 at 21:26

 | 
show 2 more comments

10

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).

share|improve this answer

edited Oct 24 ’17 at 13:54

answered Jul 31 ’17 at 18:13

Patrick RobertsPatrick Roberts

29k44 gold badges5151 silver badges9090 bronze badges

add a comment
 | 

5

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

share|improve this answer

answered Dec 8 ’17 at 12:14

Philip BijkerPhilip Bijker

3,66522 gold badges3232 silver badges3838 bronze badges

Not stable for primitive types or duplicate elements in array. jQuery.expando.split( “” ).sort( ( a, b ) => 0 ).join( “” ) === jQuery.expando

– martian
May 4 ’18 at 9:42

add a comment
 | 

3

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.

share|improve this answer

edited May 23 ’17 at 12:10

Community♦

111 silver badge

answered Dec 24 ’13 at 23:41

goatgoat

28.3k66 gold badges6161 silver badges8787 bronze badges

Are your benchmark correct? Seems, your “stableSort” does not modify input array, other sorts – do, and as you did not recreate “arr” during “setup”, other sorts sort already sorted arrays….

– 4esn0k
Mar 13 ’16 at 18:56

@4esn0k did you read wrong? I said my stableSort func was NOT fast.

– goat
Mar 24 ’17 at 3:12

@gota, ah, pardon me

– 4esn0k
Mar 25 ’17 at 11:16

add a comment
 | 

3

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.

share|improve this answer

edited Jun 27 ’18 at 21:46

answered Jul 27 ’15 at 15:22

David LeppikDavid Leppik

2,8242424 silver badges1717 bronze badges

add a comment
 | 

1

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));

share|improve this answer

answered Jul 29 ’12 at 17:35

demosthenesdemosthenes

93811 gold badge1010 silver badges1717 bronze badges

add a comment
 | 

0

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.

share|improve this answer

edited Jun 24 ’14 at 23:34

answered Jun 24 ’14 at 23:13

alfadog67alfadog67

76266 silver badges2626 bronze badges

add a comment
 | 

0

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”https://stackoverflow.com/”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’);

share|improve this answer

answered Jul 13 ’16 at 18:37

Cumulo NimbusCumulo Nimbus

5,25644 gold badges3535 silver badges5858 bronze badges

add a comment
 | 

0

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 */
};

You now instead use:

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

share|improve this answer

edited Feb 27 ’17 at 11:54

answered Dec 15 ’16 at 15:08

JobJob

52844 silver badges1111 bronze badges

add a comment
 | 

0

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)

share|improve this answer

edited Jul 10 ’19 at 20:37

answered Jul 10 ’19 at 19:24

MathiasMathias

1,3161111 silver badges1515 bronze badges

add a comment
 | 

0

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.

share|improve this answer

answered Feb 13 at 0:40

akaltarakaltar

7971616 silver badges2222 bronze badges

add a comment
 | 

-1

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

share|improve this answer

edited Nov 10 ’11 at 9:38

The_Fox

6,76422 gold badges3535 silver badges6464 bronze badges

answered Jul 25 ’11 at 17:59

Jericho WestJericho West

1522 bronze badges

12

A few things to be said: 1. Counting sort only works well in a dense number space. (Try sorting the array [1, 2e9, 1e9]) 2. Don’t write for loops as while loops. 3. Don’t randomly add things to the Math namespace. 4. You might want to consider making friends with semicolons.

– Domi
Jan 7 ’14 at 9:00

Also, in case where array has duplicate values, it will run forever. For example, array [3, 1, 3] hashes to [undefined, 1, undefined, 3]. We get two non-undefined values, while algorithm expects there to be three of them.

– MKPS
Jun 29 ’16 at 14:30

add a comment
 | 

Your Answer

Thanks for contributing an answer to Stack Overflow!Please be sure to answer the question. Provide details and share your research!But avoid …Asking for help, clarification, or responding to other answers.Making statements based on opinion; back them up with references or personal experience.To learn more, see our tips on writing great answers.

Draft saved
Draft discarded

Sign up or log in

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Submit

Post as a guest

Name

Email
Required, but never shown

Post Your Answer

Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you’re looking for? Browse other questions tagged javascript algorithm sorting or ask your own question.

The Overflow Blog

Podcast Episode 220: Fully Remote

Tracking down performance pitfalls in Vue.js

Featured on Meta

Planned maintenance scheduled for Saturday, March 28, 2020 at 13:00 UTC (9AM…

An Update On Creative Commons Licensing

Community and Moderator guidelines for escalating issues via new response…

How does the Triage queue work?

Triage needs to be fixed urgently, and users need to be notified upon…

Linked

3

Weird behavior in sorting JavaScript array

0

Why is the Array.sort() method in my Javascript program unstable?

2

Sort in javascript – ignore sort when same value

0

why is .sort return 0 reordering my results?

2

Sort Alphabetically without rearranging duplicates

0

javascript how sort array of objects by two rule?

226

Javascript Array.sort implementation?

60

Sorting JSON by values

64

What is the stability of the Array.sort() method in different browsers?

39

Javascript: Sort array and return an array of indicies that indicates the position of the sorted elements with respect to the original elements

see more linked questions…

Related

7639How do JavaScript closures work?6028How do I remove a property from a JavaScript object?3922How do I check if an array includes a value in JavaScript?3422How do I sort a dictionary by value?5085How do I include a JavaScript file in another JavaScript file?7474What does “use strict” do in JavaScript, and what is the reasoning behind it?7428How to check whether a string contains a substring in JavaScript?2459Storing Objects in HTML5 localStorage8014How can I remove a specific item from an array?1629Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition

Hot Network Questions

Restore a BASIC program after reset or “NEW” command on a Commodore 128

Does anyone know a way to use patterns in Query?

Cook me a character meal

What’s the point of Super Star Destroyers?

Create an ISO of an AWS EC2 Server

How much of the US media referred to the COVID-19 as the “Wuhan Virus” until it received an official designation from the WHO?

Pendulum Encoding

Four distinct 8-bit integers

How to make bread with plain flour?

Why John 1:1 in DRB is not literal translation from the Latin Vulgate?

Cat Keeps Drinking Unattended Drinks

cannot recall name/author of sci-fi short story about extra sense that can be experienced by humans only once (probably from 1960’s or 70’s)

What does the red R in old manual lenses mean?

Identifying the subject of a sentence

I have a YMA Visa – will Germany let me into the country despite COVID-19?

Does liquid temperature matter when making bread in a bread maker?

Separating lanthanides using ion-exchange method

What to do when a taxi driver uses the meter but at the end of the ride clears the meter and pretends we had agreed on some higher price for the ride?

How do “tip jet” helicopters cancel the torque effect of the main rotor?

Could I still play cards from the activated ability of Golos while the Epic effect is active?

Why would a ‘first world’ alien opt to have a brood of dumb children rather than one smart one?

Word for a small cylindrical glass container (for salves, creams etc.)

Confused with the effect number of decimals at the output of transducer

When I burn isopropyl alcohol (IPA), it burns orange. But when I burn ethyl alcohol, it burns totally blue. Why is this?

more hot questions

Question feed

Subscribe to RSS

Question feed
To subscribe to this RSS feed, copy and paste this URL into your RSS reader.

lang-js

Leave a Reply

Your email address will not be published. Required fields are marked *