Три класичні парадигми проектування алгоритмів на одному прикладі — сортуванні масиву. Merge Sort і Quick Sort — це "розділяй і володарюй": задача рекурсивно дробиться на менші, розв'язується там, а результати комбінуються. Bubble Sort — наївний перебірний підхід без розбиття, показаний для порівняння.
T(n) = 2·T(n/2) + O(n) → O(n·log₂n) (Merge / Quick — середній випадок)
T(n) = T(n-1) + O(n) → O(n²) (Bubble — найгірший і середній випадок)
- Merge Sort — ділить масив навпіл до одиничних елементів, потім зливає відсортовані половини за O(n) на рівень злиття; глибина рекурсії log₂n → загалом O(n log n), стабільно, завжди.
- Quick Sort — обирає опорний елемент (pivot), розбиває масив на менші/більші за нього (партиціонування), рекурсивно сортує частини; в середньому O(n log n), у гіршому — O(n²).
- Bubble Sort — послідовно міняє місцями сусідні елементи не за порядком; просто, але O(n²) порівнянь навіть у типовому випадку — тому панель показує теоретичну межу поруч із фактичним лічильником порівнянь.
Це демонструє ключову ідею аналізу складності: вибір парадигми проектування алгоритму напряму визначає, як швидко зростає час роботи зі збільшенням n.