Javascript's sort is 'unstable' - how do I get around this?

Question

According to the MDN spec, Javascript's sort() function is 'unstable' (does not maintain input order for identical elements).

Ironically, it seems that Firefox currently doesn't implement this - but Chrome appears to.

This leaves me with a bit of an issue. I have a set of elements to sort - once sorted I'd like to flag them as 'sorted' so that subsequent attempts to sort will not waste a lot of time discovering they're already sorted (I can unflag them if anything changes).

Problem is, my solution for this is returning '0' in my compare function, but that means I'm simply returning 'equivalence' for every element and they can (and will) be shuffled.

This demonstrates the problem (fiddle here)

<head>
    <script>
        var firsttime=true;
        function test() {
            debugger;
            var elements = document.getElementById('test').children;
            var sortMe = [];
            for (var i=0; i<elements.length; i++)
                sortMe.push(elements[i]);
            sortMe.sort(function(a, b) {
                if (firsttime) {
                    if (a.innerText < b.innerText) return -1;
                    else if (a.innerText > b.innerText) return 1;
                    else return 0;
                } else {
                    return 0;
                }
            });
            var parent = document.getElementById('test');
            parent.innerHTML = "";
            for(var i = 0, l = sortMe.length; i < l; i++) {
                parent.appendChild(sortMe[i]);
            }
            firsttime=false;
        }
    </script>
</head>
<body>
<div id=test>
    <div>B</div>
    <div>D</div>
    <div>A</div>
    <div>C</div>
    <div>E</div>
    <div>B</div>
    <div>D</div>
    <div>A</div>
    <div>C</div>
    <div>E</div>
    <div>B</div>
    <div>D</div>
    <div>A</div>
    <div>C</div>
    <div>E</div>
</div>
<input type=button onclick=test()>
</body>

Run on Chrome you will see the middle element of the set move around on subsequent sorts - this doesn't happen on Mozilla (at least not the version I have here).

Any ideas on how I can work around this without having to resort EVERY time?? The actual sort is much more complex and has 100s of elements to check so takes a LOT of time which I don't want to repeat unnecessarily?

Editted to add: I even tried using the array index to force sorting the array in-order but even that doesn't work on Chrome. Chrome appears to use a variant of a Quicksort which swaps elements in the array 'just for the hell of it'

Seems I've no option but to either resort every time, skip the sort entirely or implement my own algorithm...

Do you have a secondary sort key available that would give you a unique ordering? — mu is too short, Sep 02 '13 at 02:23
In the actual application, the sort is a complex algorithm which looks at DIV content, so looking for a secondary sort would be equally slow. I'm begining to think I just mark the whole thing as 'clean' or 'dirty' and simply make no attempt to sort whatsoever unless it's marked 'dirty' - I just thought this way I could only sort the bits which had changed... — , Sep 02 '13 at 02:37
Unless... I add a sort position to the elements and use that instead - that might work but it's still "some work" as opposed to "no work". The unstable thing means you have to do 'some work' tho I guess? — , Sep 02 '13 at 02:38
There's no reason why you *must* use the Javascript `sort` function (when an unstable sort is not appropriate). You could always use your own stable sort algorithm (implementations are widely available). — Greg Hewgill, Sep 02 '13 at 02:49
This is, of course, quite true - Do you have any suggestions for a stable sort? — , Sep 02 '13 at 09:57
@JohnPeat: You could try the answers to this question: [Fast stable sorting algorithm implementation in javascript](http://stackoverflow.com/questions/1427608/fast-stable-sorting-algorithm-implementation-in-javascript) — Greg Hewgill, Sep 02 '13 at 22:05
Uh, that comparison function is completely inconsistent. You cannot expect that it will be called only once and be able to infer the correct order for even a single element from that first result. Your `firsttime` is what would break *every* sorting algorithm, stable or not. Notice that there isn't even much to optimise there - the standard algorithms do quite well on nearly-sorted arrays already. — Bergi, Jun 15 '17 at 08:59

score 5 · Answer 1 · answered Sep 03 '13 at 02:41

Here is an example of a working stable sort. It adds an extra parameter for the original item index which is used if items are otherwise "equal". The code should work in any browser in use.

Note that it is an example only and should be modified to suit your particular circumstance.

<script type="text/javascript">

// Return the text content of an element depending on
// whether the textContent or innerText property is supported
function getText(el) {
  if (typeof el.textContent == 'string') {
    return el.textContent;
  } else if (typeof el.innerText == 'string') {
    return el.innerText;
  } else {
    // gather text nodes and concatenate values
    // trimmed as almost never used now
  }
}


function sortEm(){

  // Get the elements to sort
  var container = document.getElementById('container'); 
  var divs = container.getElementsByTagName('div');
  var els = [];

  // Convert collection to an array, add the current index for the element
  // as a data- property
  for (var i=0, iLen=divs.length; i<iLen; i++) {
    divs[i].setAttribute('data-sortIndex', i);
    els[i] = divs[i];
  }

  // Sort the array. If the textContent is equal, use
  // the original index
  els.sort(function(a, b) {
    var aText = getText(a);
    var bText = getText(b);

    if (aText < bText) return -1;
    if (aText > bText) return 1;
    return a.getAttribute('data-SortIndex') - b.getAttribute('data-sortIndex');
  })

  // Modify the content
  for (var j=0, jLen=els.length; j<jLen; j++) {
    container.appendChild(els[j]);
  }
}

</script>

<div id="container">
  <div style="background-color: red;">0</div>
  <div style="background-color: red;">2</div>
  <div style="background-color: blue;">0</div>
</div>
<button onclick="sortEm()">Sort divs</button>

The extra parameter is added as an attribute and could be removed when elements are added back to the container to keep things clean.

Oh, an alternative to the above is to create an object and use the textContent + index as property names and the elements as values. The sort the property names (the sort function will need to split the index off so it's compared as a number if all else is equal), then use the sorted array to put the elements in the correct order. This method avoids adding and removing attributes and properties directly on the elements (much preferred by some). — RobG, Sep 03 '13 at 03:04

Javascript's sort is 'unstable' - how do I get around this?

1 Answers1

Linked

Related