Алгоритми сортування візуально — бульбашкове, злиттям, швидке, пірамідальне, підрахунком і порозрядне

1. Нижня межа сортування порівнянням

2. Прості сортування O(n²)

Сортування вставками

Найкраще підходить для: майже відсортованих даних, малих масивів (n < 50), потокових даних (сортування в міру надходження елементів). O(n) у найкращому випадку на відсортованому вході.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

Бульбашкове сортування

O(n²) у найгіршому/середньому випадку, O(n) у найкращому. Просте, але рідко використовується в продакшені — сортування вставками має кращі сталі множники для малих n.

Сортування вибором

Знаходить мінімальний елемент і ставить його на початок. Завжди O(n²). Примітне мінімізацією перестановок (лише n перестановок загалом) — корисне, коли записи дорогі (наприклад, флеш-пам'ять).

3. Сортування злиттям

Поділяй і володарюй: розбити навпіл, рекурсивно відсортувати кожну половину, злити дві відсортовані половини.

Висхідне сортування злиттям уникає накладних витрат на рекурсію, зливаючи серії розміром 1, 2, 4, 8, ... — використовується в Arrays.sort у Java та Timsort у Python (який використовує наявні відсортовані серії для O(n) на майже відсортованому вході).

4. Швидке сортування

5. Пірамідальне сортування

6. Сортування за лінійний час

Уникаючи поелементних порівнянь і використовуючи структуру даних, деякі алгоритми сортують за час O(n) — перемагаючи нижню межу порівнянь Ω(n log n):

Сортування підрахунком — O(n + k)

Для цілих чисел у діапазоні [0, k]. Підрахувати входження, потім обчислити префіксні суми, щоб визначити фінальні позиції. O(n + k) за часом і пам'яттю. Стабільне. Практичне, коли k = O(n).

Порозрядне сортування — O(d·(n + k))

Сортувати спершу за найменш значущою цифрою (LSD-порозрядне сортування), використовуючи стабільне сортування (підрахунком) на кожній з d позицій цифр. Цифри в основі b: d = ⌈log_b(макс. значення)⌉. Обрати b = n для O(n) загалом з b-цифровим поданням. Використовується в сортуванні на GPU, розподілених системах.

Блочне сортування — O(n) у середньому

Для рівномірно розподілених дійсних чисел у [0,1). Створити n блоків, що покривають [0,1); розкидати кожен елемент у його блок; відсортувати кожен блок сортуванням вставками; об'єднати. Очікувано O(n), якщо вхід рівномірний. Найгірший випадок O(n²), якщо всі елементи потрапляють в один блок.

7. Порівняльна таблиця