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

Разделить, отсортировать, слить

Сортировка слиянием использует подход «разделяй и властвуй». Массив делится пополам, каждая половина сортируется тем же способом, а затем две уже отсортированные части объединяются в одну. Главная работа происходит именно на этапе слияния.

static void merge(int[] a, int left, int mid, int right, int[] tmp) {
    int i = left;
    int j = mid;
    int k = left;

    while (i < mid && j < right) {
        tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < right) tmp[k++] = a[j++];

    for (int p = left; p < right; p++) {
        a[p] = tmp[p];
    }
}

Поскольку обе части уже отсортированы, достаточно смотреть только на их текущие первые необработанные элементы. Меньший переносится во временный массив, после чего соответствующий указатель двигается дальше. Каждый элемент участвует в слиянии один раз на каждом уровне разбиения.

Откуда берётся O(n log n)

На каждом уровне рекурсии суммарно обрабатывается O(n) элементов, а число уровней составляет O(log n), потому что размер задачи каждый раз делится примерно пополам. Итоговая временная сложность — O(n log n) независимо от исходного порядка данных.

Цена предсказуемой скорости

Для обычной реализации над массивом нужен вспомогательный массив размером O(n). Это важное отличие от сортировок, которые переставляют элементы только внутри исходного массива. Зато время работы merge sort остаётся предсказуемым даже на неудачно расположенных данных.