Сортиране чрез сливане

В информатиката сортирането чрез сливане е алгоритъм за сортиране, базиран на сравняване, който има сложност Θ(nlogn). Алгоритъмът се гради на принципа „разделяй и владей“. Създаден е от Джон фон Нойман през 1945.

Принцип на действие

1. Несортирания списък по произволен начин се разделя на два подсписъка с приблизително обща дължина (за линейно време)
2. Рекурсивно се разделят подсписъците, докато не се достигне до списъци с единична дължина
3. Сливат се два подсписъка в нов сортиран списък (за линейно време)