Merge sort (сортування злиттям)


Переходимо до більш просунутих алгоритмів сортування. Merge sort є одним з найшвидших алгоритмів сортування з time complexity O(n log n) - найкраща, що ми маємо наразі для сортування універсальних датасетів (кращу average time complexity можуть мати алгоритми, які працюють тільки з окремими типами даних, найчастіше з числами, але це нам наразі не так цікаво).

Merge sort працює за принципом розділяй та володарюй (divide and conquer). Перше припущення, яке ми тут робимо - датасети(масиви), що мають один або нуль елементів завжди є сортованими. Тобто isSorted([]), isSorted[2], isSorted[‘g’] завжди є true.

Відповідно нашою задачею є розділити великий масив на підмасиви з сортованих елементів і потім рекурсивно змерджити ці масиви в один сортований.

Розділення на масиви має time complexity O(log n). Злиття двох сортованих масивів в один сортований - це луп з O(n). Звідси маємо загальну time complexity mergeSort O(n log n).

Код: https://codepen.io/olenitut/pen/OJKaBYN?editors=0011
Стаття з візуалізацією процесу: https://www.geeksforgeeks.org/merge-sort/