Сортування злиттям (merge sort)

Коротко: Сортування злиттям ділить список на дві половини, рекурсивно сортує обидві й зливає відсортовані половини у відсортований список. Вона працює за O(n log n) у будь-якому випадку й стійка.

Докладніше: На відміну від швидкого сортування, у сортування злиттям немає поганого особливого випадку; натомість їй потрібна додаткова пам’ять O(n). Вона добре підходить для зв’язних списків і для сортування даних, що не вміщуються в оперативну пам’ять (зовнішнє сортування).

Подробиці

def merge_sort(items):
    if len(ite

Див. також: швидке сортування, сортування бульбашкою, сортування, рекурсія