Яка складність у найшвидшого сортування? Чому не можна зробити швидше?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Для будь-яких універсальних порівняльних сортувань мінімально досяжна асимптотика - Θ(n log n) за кількістю порівнянь (у середньому і в найгіршому випадках). Швидше зробити не можна, тому що будь-яке порівняльне сортування повинно розрізнити n! перестановок, а бінарне дерево рішень вимагає щонайменше log2(n!) ≈ n log2 n - 1.44n порівнянь. Лінійний час O(n) можливий лише за додаткових обмежень на ключі (наприклад, цілі числа з обмеженого діапазону - counting/radix sort).

Детальний розбір

Межі для порівняльних сортувань

Нижня межа: будь-яке порівняльне сортування вимагає Ω(n log n) порівнянь.
Верхня межа: існують алгоритми зі складністю O(n log n) - merge sort, heap sort (у найгіршому випадку), quicksort (у середньому випадку).
Підсумок: оптимальна асимптотика для порівняльних алгоритмів - Θ(n log n). Основа логарифма не має значення (відрізняється константою).

Інтуїція доведення через дерево рішень

Будь-яке порівняльне сортування - це послідовність запитань виду «a[i] ≤ a[j]?». Його роботу можна подати бінарним деревом рішень, де кожен вузол - порівняння, а лист - остаточний порядок.
Різних входів (перестановок) - n!, отже, листків не менше n!.
Бінарне дерево з L листками має глибину щонайменше log2 L, отже, глибина ≥ log2(n!). Це і є мінімальна кількість порівнянь у найгіршому випадку.
За формулою Стірлінга: log2(n!) ≈ n log2 n - 1.44n + O(log n). Отже, нижня межа - Ω(n log n).

Передумови моделі (чому це справедливо)

Ми рахуємо лише порівняння ключів; кожна операція порівняння дає не більше 1 біта інформації.
Ключі довільні й неструктуровані (їх не можна «розкладати по кошиках» без порівнянь).
Модель RAM з однаковою вартістю елементарних операцій.

Коли можна швидше за O(n log n)

Counting sort: O(n + k), де k - розмір діапазону цілих ключів. Вимагає, щоб ключі були невеликими цілими числами (наприклад, з [0, k)).
Radix sort: O(n · d) за кількістю розрядів (або O(n log_k U) для основи k і діапазону U), працює для фіксованої довжини ключів/розрядів (рядки фіксованої довжини, 32/64-бітні цілі).
Bucket sort: очікувано O(n) за «хорошого» розподілу даних (наприклад, рівномірного на [0,1)).
Підсумок: лінійне сортування можливе, коли ми використовуємо структуру ключів (обмежений діапазон, фіксована довжина, припущення про розподіл). У загальному випадку без цих передумов - не можна.

Практичні алгоритми та їхня складність

Merge sort - O(n log n) у найгіршому випадку, стабільний, але вимагає O(n) дод. пам'яті.
Heap sort - O(n log n) у найгіршому випадку, майже in-place, нестійкий, гірші константи/локальність.
Quick sort - у середньому O(n log n), найгірший випадок O(n^2) (див. випадкові опорні елементи/median-of-three для зниження ризику), in-place, відмінна кеш-локальність.
Timsort (у Python/Java) - найгірший випадок O(n log n), адаптивний: для майже відсортованих даних може бути близьким до O(n).

Приклад коду: сортування O(n log n) (Merge Sort, JS)

javascript

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

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

// Приклад використання:
// const arr = [5, 1, 4, 2, 8];
// console.log(mergeSort(arr)); // [1, 2, 4, 5, 8]

Приклад коду: O(n) за обмеженого діапазону (Counting Sort, JS)

javascript

function countingSort(arr, min, max) {
  const k = max - min + 1;
  const count = new Array(k).fill(0);

  for (const x of arr) {
    if (x < min || x > max) throw new Error('ключ поза діапазоном');
    count[x - min]++;
  }

  let idx = 0;
  for (let i = 0; i < k; i++) {
    while (count[i]-- > 0) arr[idx++] = i + min;
  }
  return arr;
}

// Приклад використання:
// const arr = [5, 1, 4, 2, 8, 2];
// console.log(countingSort(arr, 0, 10)); // [1, 2, 2, 4, 5, 8]
// Важливо: працює ефективно, коли (max - min) = O(n).

Підсумки

Сортування загального призначення на основі порівнянь не може бути швидшим за Θ(n log n) - це інформаційно-теоретична нижня межа.
Лінійні алгоритми сортування можливі лише за додаткових припущень про ключі або їхній розподіл.
На практиці обирайте алгоритм під обмеження задачі: діапазон ключів, стабільність, пам'ять, розподіл даних.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.