Какова устойчивость Array.sort () метод в различных браузерах?

Я хотел бы поделиться трюком, который я обычно использую в C / C ++ для qsort () .

JS sort () позволяет указать функцию сравнения. Создайте второй массив такой же длины и заполните его увеличивающимися числами от 0.

function stableSorted(array, compareFunction) {
  compareFunction = compareFunction || defaultCompare;
  var indicies = new Array(array.length);
  for (var i = 0; i < indicies.length; i++)
    indicies[i] = i;

Это индексы в исходном массиве. Мы собираемся отсортировать второй массив. Сделайте настраиваемую функцию сравнения.

  indicies.sort(function(a, b)) {

Он получит два элемента из второго массива: использует их в качестве индексов в исходных массивах и сравнит элементы.

    var aValue = array[a], bValue = array[b];
    var order = compareFunction(a, b);
    if (order != 0)
      return order;

Если элементы совпадают, сравните их индексы, чтобы сделать порядок стабильным.

   if (a < b)
     return -1;
   else
     return 1;
  });

После sort () второй массив будет содержать индексы, которые вы можете использовать для доступа к элементам исходного массива в стабильном отсортированном порядке.

  var sorted = new Array(array.length);
  for (var i = 0; i < sorted.length; i++)
    sorted[i] = array[indicies[i]];
  return sorted;
}

// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
  a = String(a);
  b = String(b);
  if (a < b) return -1;
  else if (a > b) return 1;
  else return 0;
}

В общем, стабильные алгоритмы сортировки только созревают и по-прежнему требуют больше дополнительной памяти по сравнению со старым добрым qsort. Думаю, именно поэтому очень немногие спецификации требуют стабильной сортировки.

Если вы ищете список браузеров, в которых следует использовать неродной алгоритм сортировки, мое предложение - не делать.

Вместо этого проверьте вменяемость сортировки при загрузке скрипта и на основании этого принимайте решение.

Поскольку спецификация не требует определенного поведения в этом отношении, она не застрахована от последующих изменений, даже в пределах одной и той же строки браузера.

Вы можете отправить патч на http://www.browserscope.org/, чтобы включить такие тесты в их набор. Но опять же, обнаружение функций превосходит обнаружение браузеров.