Stable Sort

Stable Sort Implementation and Test

by simo

JavaScript

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)
  
  // 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 }
  ]
  
  
var stable = stableSort(input, (a, b) => a.height - b.height)
var unstable = new Array(...input).sort((a, b) => a.height - b.height)

var render = (arr) => arr.reduce((list, {height, weight}) =>
  list += `<div>height: ${height}, weight: ${weight}</div>`, '')

document.querySelector('body').innerHTML +=
  '<h1>stableSort()</h1>' + render(stable) +
  '<h1>Array.sort() - should be unstable in Chrome/NodeJS</h1>' + render(unstable)