JavaScript で安定ソート

めも。

// デフォルトの比較関数
function compare (a, b) {
  if (a === b) {
    return 0;
  } else if (a > b) {
    return 1;
  } else {
    return -1;
  }
}

function stableSort (array, fn) {
  if (fn == null) {
    fn = compare;
  }

  var i, len = array.length;

  if (len === 0) return array;

  // 値とインデックスのペアにする
  for (i = 0; i < len; i++) {
    array[i] = [array[i], i];
  }

  array.sort(function (p1, p2) {
    var cmp = fn(p1[0], p2[0]);
    if (cmp !== 0) {
      // ペアの0番目同士が等しくない場合はその比較結果を返す
      return cmp;
    } else {
      // 等しい場合は、インデックスを比較した結果を返す
      return p1[1] - p2[1];
    }
  });

  // ペアの0番目を取り出す
  for (i = 0; i < len; i++) {
    array[i] = array[i][0];
  }

  return array;
}