Сортировка слиянием (merge sort)

Коротко: Сортировка слиянием делит список на две половины, рекурсивно сортирует обе и сливает отсортированные половины в отсортированный список. Она работает за O(n log n) в любом случае и устойчива.

Подробнее: В отличие от быстрой сортировки, у сортировки слиянием нет плохого особого случая; взамен ей нужна дополнительная память O(n). Она хорошо подходит для связных списков и для сортировки данных, не помещающихся в оперативную память (внешняя сортировка).

Подробности

def merge_sort(items):
    if len(ite

См. также: быстрая сортировка, сортировка пузырьком, сортировка, рекурсия