сортировка слиянием

EN: merge sort

Алгоритм сортировки «разделяй и властвуй», рекурсивно делящий массив пополам, сортирующий каждую половину и затем объединяющий их. Время — O(n log n) во всех случаях: лучшем, среднем и худшем. Устойчив, требует O(n) дополнительной памяти; в отличие от быстрой сортировки, не деградирует до O(n²).