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

Условие

Реализуйте сортировку слиянием для массива nums.

Решение

Идея

Делим массив пополам, рекурсивно сортируем половины, сливаем два отсортированных в один.

Код (Python)

class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        def merge(a: list[int], b: list[int]) -> list[int]:
            i = j = 0
            out = []
            while i < len(a) and j < len(b):
                if a[i] <= b[j]:
                    out.append(a[i]); i += 1
                else:
                    out.append(b[j]); j += 1
            out.extend(a[i:])
            out.extend(b[j:])
            return out
 
        def sort(arr: list[int]) -> list[int]:
            if len(arr) <= 1:
                return arr
            mid = len(arr) // 2
            return merge(sort(arr[:mid]), sort(arr[mid:]))
 
        return sort(nums)

Сложность

• Время: O(n log n) — всегда.
• Память: O(n) — на временные буферы.
• Стабильна: да.

Сравнение с быстрой сортировкой

• Merge sort даёт гарантированный O(n log n). Quicksort — O(n^2) в худшем случае.
• Merge sort — O(n) доп. памяти. Quicksort — O(log n) стек.
• Merge sort стабильна, quicksort — нет.
• Из-за памяти на массивах целых обычно используют quicksort, на связанных списках — merge sort (там память не нужна).

Подводные камни

1. <= в сравнении. a[i] <= b[j] сохраняет стабильность (берём из левой при равенстве).
2. O(n) памяти. Если запретили — bottom-up merge sort с массивом-двойником, либо in-place merge sort (сложнее, не стандартно).
3. Глубина рекурсии. O(log n) — для n = 10^9 это ≤ 30, ничего страшного.

Эталонный ответ

Рекурсивное деление + слияние двумя указателями. O(n log n) времени, O(n) памяти, стабильна.