Javascript sort array by length instability

Question

I need to sort an array of strings by their length, leaving the strings in their original order if they are of the same length. This is my code:

arr.sort(function(a, b) {
  return b.length - a.length;
});

It works until the number of elements with the same length > 10, but after that the instability in the sort method changes the order. I have tried to find a way to keep the order the same, but I'm not having any luck. Any suggestions?

Stability is a property of the sorting algorithm. Javascript `sort` is **not** stable, so you have to work around this by first creating a new array `arr2` of pairs `(el, i)` where `el` is the element of `arr` at position `i`, then sort these pairs lexicographically, finally strip down the second `i` element. Alternatively write your own custom stable sorting algorithm (e.g. merge sort). — Bakuriu, Jun 26 '16 at 16:48
See http://stackoverflow.com/questions/1427608/fast-stable-sorting-algorithm-implementation-in-javascript — elclanrs, Jun 26 '16 at 16:48

score 1 · Answer 1 · answered Jun 26 '16 at 16:49

1

You have to sort pairs (element, index) instead of actual elements. This way you'll have stable sort.

answered Jun 26 '16 at 16:49

Qumeric

518
5
16

Thomas · Answer 2 · 2016-06-26T17:21:24.160

arr.map(function(str, i){
    return {
        index: i,
        length: str.length,
        value: str
    }
}).sort(function(a, b){
    return b.length - a.length || a.index - b.index;
}).map(function(obj){
    return obj.value;
})

This may seem like to much overhead, but as soon as you have to somehow compute the value you are sorting on, it's faster to compute it once and store it to some Object, than computing it potentially in a n*(n-1) operation.

So this approach in sorting is often the more performant one.

Or you generallize the two mapping-tasks:

var valueIndex = function(value,index){ return {value:value,index:index} };
var getValue = function(obj){ return obj.value };

arr.map(valueIndex)
    .sort(function(a, b){ 
        return b.value.length - a.value.length || a.index - b.index
    })
    .map(getValue);

ES6

var valueIndex = (value,index) => { return {value,index} };
var getValue = ({value}) => value;

arr.map(valueIndex)
    .sort((a, b) => b.value.length - a.value.length || a.index - b.index)
    .map(getValue);

Nina Scholz · Answer 3 · 2016-06-26T17:10:52.033

You could use sorting with map, where the map contains the length and the index of original sorting.

// the array to be sorted
var stringArray = ['Tom', 'Mia', 'Michael', 'Bob', 'Thomas', 'Joy'];

// temporary array holds objects with position and sort-value
var mapped = stringArray.map(function (el, i) {
    return { index: i, value: el.length };
});

// sorting the mapped array containing the reduced values
mapped.sort(function (a, b) {
    return b.value - a.value || a.index - b.index;
});

// container for the resulting order
var result = mapped.map(function (el) {
    return stringArray[el.index];
});

console.log(result);

Javascript sort array by length instability

3 Answers3