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...
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…
