Как работает сортировка массива по возрастанию

kirilljsx

Вы когда ни будь задумывались как работает сортировка массива изнутри? Мы все давным давно привыкли и даже не задумываемся над такими вещами, но я все же хочу осветить работу нашу любимого JavaScript под капотом.

Начнем разбираться, у нас есть массив цифры и нам нужно его отсортировать по возрастанию, как мы будем это делать? Конечно же используем .sort() :

const nums = [40, 100, 1, 5, 25, 10];
nums.sort((a, b) => a - b);
console.log(nums); // [1, 5, 10, 25, 40, 100]

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

В методе sort() аргументы a и b - это два конкретных элемента массива, которые JavaScript берет для попарного сравнения в текущий момент работы алгоритма сортировки.

Алгоритм сортировки «под капотом» (часто QuickSort или Timsort, в зависимости от браузера) проходит по массиву и постоянно задает вопрос: «Кто из этих двоих должен стоять раньше?».

Как это работает в (a, b) => a - b

Функция должна вернуть число. Знак этого числа (плюс, минус или ноль) говорит сортировщику, что делать с a и b.

Результат выражения `a` - `b`	Значение	Действие сортировщика
Отрицательное (`< 0`)	`a` меньше `b`	Оставляет `a` перед `b` (индекс `a` < индекса `b`)
Положительное (`> 0`)	`a` больше `b`	Меняет их местами, ставит `b` перед `a`
Ноль (`0`)	`a` равно `b`	Оставляет их порядок без изменений (в стабильных сортировках)

А теперь на пальцах:
Допустим, JS сравнивает пару 100 и 5:

a = 100, b = 5.
Считаем a - b: 100 - 5 = 95.
Результат 95 (положительное число).
Вывод: «Ага, a больше, значит, он “тяжелее” и должен уйти вправо (в конец)». 5 встанет перед 100.

Если сравнивает 5 и 25:

a = 5, b = 25.
Считаем a - b: 5 - 25 = -20.
Результат -20 (отрицательное число).
Вывод: «a меньше, он “легче”, пусть стоит слева (в начале)». Порядок сохраняется.

Таким образом, вычитание - это просто математический трюк, чтобы быстро получить нужное отрицательное или положительное число. Вот так вот и работает сортировка по возрастанию и убыванию.
Кстати если нужна сортировка по убыванию нужно поменять местами a и b вот так:

nums.sort((a, b) => b - a);