Ответ 1

TL; DR

Я всегда успешно сортировал свои массивы вроде этого

Нет, нет. И не заметил. Быстрый контрпример:

> [1,1,0,2].sort(function(a, b){ return a>b })
Array [0, 1, 2, 1]
// in Opera 12. Results may vary between sorting algorithm implementations

почему?

Поскольку ваша функция сравнения возвращает false (или 0, эквивалентно), даже если b больше, чем a. Но 0 означает, что два элемента считаются равными - и алгоритм сортировки считает, что.

Объяснение глубины

Функции сравнения в JavaScript

Как работают функции сравнения?

Метод Array::sort может принимать в качестве аргумента опциональную, настраиваемую функцию сравнения. Эта функция принимает два аргумента (обычно называемых a и b), которые он должен сравнивать, и должен возвращать число

• > 0, когда a считается больше, чем b, и его следует сортировать после него
• == 0, когда a считается равным b, и не имеет значения, что на первом месте
• < 0, когда a считается меньше b и должен быть отсортирован перед ним

Если он не возвращает число, результат будет передан в число (что удобно для булевых). Возвращаемое число не должно быть точно -1 или 0 или 1 (хотя это обычно есть).

Согласованное упорядочение

Чтобы быть последовательным, функция сравнения должна была бы выполнить уравнение

comp(a, b) == -1 * comp(b, a)
// or, if values other than -1, 0 and 1 are considered:
comp(a, b) * comp(b, a) <= 0

Если это требование нарушено, сортировка будет вести себя undefined.

Ссылаясь на спецификацию ES5.1 на sort (то же самое в ES6 spec):

Если comparefn [...] не является последовательной функцией сравнения для элементов этого массива, поведение сортировки определяется реализацией.

Функция comparefn является последовательной функцией сравнения для набора значений S, если все требования ниже удовлетворяются для всех значений a, b и c (возможно, того же значения) в наборе S: обозначение a <CF b означает comparefn(a,b) < 0; a =CF b означает comparefn(a,b) = 0 (любого знака); и a >CF b означает comparefn(a,b) > 0.

Вызов comparefn(a,b) всегда возвращает одно и то же значение v при задании определенной пары значений a и b в качестве двух аргументов. Кроме того, Type(v) - Number, а v не NaN. Заметим, что это означает, что только одна из a <CF b, a =CF b и a >CF b будет верна для данной пары a и b.

• Вызов comparefn(a,b) не изменяет этот объект.
• a =CF a (reflexivity)
• Если a =CF b, то b =CF a (симметрия)
• Если a =CF b и b =CF c, то a =CF c (transтивность =CF)
• Если a <CF b и b <CF c, то a <CF c (транзитивность <CF)
• Если a >CF b и b >CF c, то a >CF c (транзитивность >CF)

ПРИМЕЧАНИЕ. Вышеуказанные условия необходимы и достаточны для того, чтобы comparefn делит набор S на классы эквивалентности и что эти классы эквивалентности полностью упорядочены.

Что это значит? Почему меня это должно волновать?

Алгоритм сортировки должен сравнивать элементы массива друг с другом. Чтобы сделать хорошую и эффективную работу, ей не нужно сравнивать каждый элемент со всеми остальными, но он должен иметь возможность рассуждать о своем заказе. Для этого хорошо работать, существует несколько правил, которые должны соблюдать пользовательские функции сравнения. Тривиальным является то, что элемент a равен самому себе (compare(a, a) == 0) - первый элемент в списке выше (рефлексивность). Да, это немного математически, но платит хорошо.

Наиболее важным является транзитивность. В нем говорится, что когда алгоритм сравнивал два значения a и b, а также b с c и обнаружил, применяя функцию сравнения, например, a = b и b < c, тогда он может ожидать, что a < c также сохраняется. Это кажется логичным и требуется для четкого, согласованного упорядочения.

Но ваша функция сравнения не выполняет эту функцию. Давайте посмотрим на этот пример:

 function compare(a, b) { return Number(a > b); }
 compare(0, 2) == 0 // ah, 2 and 0 are equal
 compare(1, 0) == 1 // ah, 1 is larger than 0
 // let conclude: 1 is also larger than 2

по электронной почте Ой. И поэтому алгоритм сортировки может выйти из строя (в спецификации это "поведение, зависящее от реализации", то есть непредсказуемые результаты), когда он вызывается с несогласованной функцией сравнения.

Почему неправильное решение так распространено?

Так как на многих других языках существуют алгоритмы сортировки, которые не ожидают трехстороннее сравнение, а всего лишь логическое меньшее, чем оператор, С++ std::sort - хороший пример этого. Он будет просто применяться дважды с замененными аргументами, если необходимо определить равенство. По общему признанию, это может быть более эффективным и менее подверженным ошибкам, но требует больше вызовов функции сравнения, если оператор не может быть встроен.

контрпримеры

Я проверил свою функцию сравнения, и он работает!

Только по чистой случайности, если вы попробовали какой-нибудь случайный пример. Или потому, что ваш набор тестов ошибочен - неправильный и/или неполный.

Вот небольшой script, который я использовал, чтобы найти приведенный выше минимальный контрпример:

function perms(n, i, arr, cb) {
// calls callback with all possible arrays of length n
    if (i >= n) return cb(arr);
    for (var j=0; j<n; j++) {
        arr[i] = j;
        perms(n, i+1, arr, cb);
    }
}
for (var i=2; ; i++) // infinite loop
    perms(i, 0, [], function(a) {
        if (    a.slice().sort(function(a,b){ return a>b }).toString()
             != a.slice().sort(function(a,b){ return a-b }).toString() )
            // you can also console.log() all of them, but remove the loop!
            throw a.toString();
    });

Какая функция сравнения верна?

Использовать никакой функции сравнения вообще, если вы хотите использовать лексикографическую сортировку. Элементы массива при необходимости будут стягиваться.

Общая функция сравнения, которая работает как реляционные операторы, может быть реализована как

function(a, b) {
    if (a > b) return 1;
    if (a < b) return -1;
    /* else */ return 0;
}

С помощью нескольких трюков это можно уменьшить до эквивалента function(a,b){return +(a>b)||-(a<b)}.

Для чисел вы можете просто вернуть их разницу, которая соблюдает все законы выше:

function(a, b) {
    return a - b; // but make sure only numbers are passed (to avoid NaN)
}

Если вы хотите отсортировать в обратном порядке, просто возьмите соответствующий и замените a на b.

Если вы хотите сортировать композитные типы (объекты и т.д.), замените каждый a и каждый b на доступ к рассматриваемым свойствам, или вызов метода или все, что вы хотите сортировать.

Ответ 2

Функция sort ожидает функцию, которая ожидает два аргумента a и b, и возвращает:

• Отрицательное число, если a предшествует b
• Положительное число, если a приходит после b
• Нуль, если относительный порядок a и b не имеет значения.

Чтобы отсортировать числа в порядке возрастания return a - b, вы получите правильные возвращаемые значения; например:

a    b    ret
1    2    -1
3    2     1
2    2     0

С другой стороны, return a > b создает следующие возвращаемые значения:

a    b    ret      implied
1    2    false    0
3    2    true     1
2    2    false    0

В приведенном выше примере функции сортировки говорят, что 1 и 2 одинаковы (и размещение 1 до 2 или 2 до 1 не имеет значения). Это приведет к некорректному результату, например (в Chrome 49):

[5, 8, 7, 1, 2, 3, 4, 6, 9, 10, 11, 12, 13].sort(function(a, b) {
    return a > b;
});
// [4, 5, 3, 1, 2, 6, 7, 8, 9, 10, 11, 12, 13]