Сортировка 2: слиянием и быстрая

Чтобы отсортировать миллион значений, сравнивая каждую пару, нужно около 500 миллиардов сравнений; сортировке слиянием нужно около 20 миллионов.

Раздели задачу, реши половины

Способы из прошлого урока работают сразу со всем списком и расплачиваются примерно n² сравнениями. Два способа в этом уроке следуют другому плану, он называется «разделяй и властвуй». Раздели список на меньшие части, отсортируй каждую часть тем же способом, а потом объедини отсортированные части. Деление продолжается, пока в части не останется одно значение или ни одного, а список из одного значения уже отсортирован. Поскольку способ вызывает сам себя на меньших списках, он рекурсивный (рекурсию подробно разбирает урок 6).

Сортировка слиянием: вся работа в слиянии

Сортировка слиянием делит список пополам, сортирует левую половину, сортирует правую половину и сливает две отсортированные половины в одну. Хитрость в слиянии. Два отсортированных списка можно объединить, глядя только на их первые значения. Сравни два первых значения, запиши меньшее и перейди за него. Повторяй, пока один список не опустеет, затем перепиши остаток другого. Слияние [1, 4, 7] и [2, 3, 8] идёт так: 1 (1 и 2), 2 (4 и 2), 3 (4 и 3), 4 (4 и 8), 7 (7 и 8), а затем переписывается 8: 5 сравнений на 6 значений. Слиянию двух списков, в которых всего n значений, никогда не нужно больше n − 1 сравнений.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // уже отсортирован
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Почему это быстро? Представь деление пополам как уровни. Список из 8 значений делится на 2 списка по 4, затем на 4 списка по 2, затем на 8 списков по 1: три уровня, потому что 8 можно поделить пополам 3 раза. На каждом уровне все слияния вместе касаются каждого значения один раз, поэтому уровень стоит не больше примерно n сравнений. При log₂ n уровнях всего выходит около n log₂ n. Для миллиона значений это около 20 миллионов сравнений против примерно 500 миллиардов у способов, которые сравнивают пару за парой. При делении на [38, 27, 43, 3] и [9, 82, 10], как в лаборатории, список [38, 27, 43, 3, 9, 82, 10] требует 14 сравнений; код выше делит его на 3 и 4 и требует 13.

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

Быстрая сортировка: делим вокруг опорного элемента

Быстрая сортировка делит список по-другому. Она выбирает одно значение, опорный элемент, и переставляет список так, чтобы всё меньшее опорного стояло перед ним, а всё остальное после. Этот шаг называется разбиением. Теперь опорный элемент на своём окончательном месте, и две стороны можно отсортировать по отдельности тем же способом. Потом ничего сливать не нужно, потому что каждое значение слева уже меньше каждого значения справа.

Лаборатория использует распространённый учебный вариант, где опорным элементом каждой части берут последнее значение. На [5, 1, 4, 2, 8] опорный элемент 8 сравнивается с четырьмя другими значениями, все меньше, поэтому 8 остаётся в конце. Следующая часть [5, 1, 4, 2] берёт опорный элемент 2: меньше только 1, так что после двух обменов список становится [1, 2, 4, 5, 8]. Ещё одно сравнение обрабатывает [4, 5]. Итого: 8 сравнений и 2 обмена.

Когда опорный элемент оказывается около середины, каждое разбиение делит задачу пополам, и быстрая сортировка делает около n log₂ n сравнений, как сортировка слиянием. К тому же она работает внутри исходного списка без второй копии. Но плохой опорный элемент вредит. Если список уже отсортирован и опорным всегда берут последнее значение, каждое разбиение отделяет всего одно значение, и быстрая сортировка скатывается примерно к n²/2 сравнениям: 10 для [1, 2, 3, 4, 5], как у сортировки выбором. Настоящие библиотеки избегают этого, выбирая опорный элемент внимательнее, например случайно или как средний из трёх взятых значений.