Усі алгоритми отримують один і той самий масив; кожне порівняння або обмін триває однаково довго. Перемагає той, кому потрібно менше операцій.
| Алгоритм | Найкращий | Середній | Найгірший | Пам’ять |
|---|---|---|---|---|
| Бульбашкою | O(n) | O(n²) | O(n²) | O(1) |
| Вставками | O(n) | O(n²) | O(n²) | O(1) |
| Вибором | O(n²) | O(n²) | O(n²) | O(1) |
| Швидке | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Злиттям | O(n log n) | O(n log n) | O(n log n) | O(n) |
O() описує, як росте кількість операцій зі збільшенням n. Для n = 30 різниця між n² = 900 і n·log₂n ≈ 150 уже помітна; для мільйона елементів вона стає різницею між секундами й годинами. Спробуйте «майже відсортовані» дані: бульбашка і вставки стають швидкими, а вибір — ні. Для «мало різних значень» подивіться, як поводиться швидке сортування.
Лічильник «обміни/записи» для сортування злиттям рахує записи в масив, бо цей алгоритм не міняє елементи місцями, а переписує їх із тимчасового масиву. Жовтий — елементи, що порівнюються, червоний — щойно записані.