merge_sort.md

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

| Главная | Сортировки |

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Реализация

• С использованием рекурсии

Лучшее время	Среднее время	Худшее время	Память	Устойчивая	Обмены в среднем
O(n log n)	O(n log n)	O(n log n)	O(log n)	+	O(n log n)

def merge_sort(arr):
    if len(arr) <= 1:
        return

    left = arr[:len(arr) // 2]
    right = arr[len(arr) // 2:]
    merge_sort(left)
    merge_sort(right)

    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1


nums = [12, -4, 0, 4, 5, 90, -8, 1, 1, 3, -4]
merge_sort(nums)
print(nums)