Задача

3 /7


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

Теория Нажмите, чтобы прочитать/скрыть

Сортировка слиянием
Алгоритм был изобретён Джоном фон Нейманом в 1945 году.
Идея сортировки
1) Возьмем массив. Если он состоит из одного элемента, то он уже отсортирован
2) Если элементов больше, чем один, то разобьем массив на две равные части (с точностью до единицы) и отсортируем каждую часть, применив рекурсивно тот же алгоритм. 
3) Далее, "сольем" все отсортированные части в один массив.
 
Как "слить" все части в один массив?
  1. Будем хранить индексы начала двух отсортированных частей.
  2. Создадим новый список следующим образом:
    1. из двух элементов, на которые указывают индексы, будем выбирать меньший и дописывать его в новый список;
    2. сдвинем индекс, элемент которого мы взяли, на следующий элемент списка;
    3. если закончились элементы в одной из сливаемых частей, то элементы второй мы просто добавим в конец итогового списка.
  3. Полученный отсортированный список необходимо поместить на место сливаемых частей.
 
Псевдокод алгоритма слияния
Функция сливает две части массива a - [left;mid) и [mid;right)
 
ФУНКЦИЯ merge(a, left, mid, right)    // a - массив, размерностью n; left, mid, right - целые числа, индексы элементов массива
    it1 = 0
    it2 = 0
    result: int[right - left]   // результирующий массив
  
    ПОКА left + it1 < mid И mid + it2 < right
        ЕСЛИ a[left + it1] < a[mid + it2]
            result[it1 + it2] = a[left + it1]
            it1 += 1
        ИНАЧЕ
            result[it1 + it2] = a[mid + it2]
            it2 += 1
  
    ПОКА left + it1 < mid
        result[it1 + it2] = a[left + it1]
        it1 += 1
  
    ПОКА mid + it2 < right
        result[it1 + it2] = a[mid + it2]
        it2 += 1
  
    ДЛЯ i ОТ 0 ДО it1 + it2
        a[left + i] = result[i]

    ВЕРНУТЬ a
 
 
Рекурсивный алгоритм сортировки слиянием
Функция сортирует подотрезок массива с индексами в полуинтервале  [left; right)
 
ФУНКЦИЯ mergeSortRecursive(a, left, right)    // a - массив, left, right - индексы полуинтервала сортировки
    if left + 1 >= right
        ВЕРНУТЬ a
    mid = (left + right) / 2
    mergeSortRecursive(a, left, mid)
    mergeSortRecursive(a, mid, right)
    merge(a, left, mid, right)
    ВЕРНУТЬ a

 
Итеративный алгоритм сортировки слиянием
При итеративном алгоритме используется на O(logn) меньше памяти, которая раньше тратилась на рекурсивные вызовы.
ФУНКЦИЯ mergeSortIterative(a, n) // a - массив; n - длина массива
    ДЛЯ i ОТ 1 ДО n, ШАГ i *= 2
        ДЛЯ j ОТ 0 ДО n - i, ШАГ j += 2 * i
            merge(a, j, j + i, min(j + 2 * i, n))
    ВЕРНУТЬ a
 
Время работы
Для оценки времени работы, составим рекуррентное соотношение.
Пусть T(n) - время сортировки массива длины n, тогда для сортировки слиянием справедливо:
T(n) = 2T(n/2)+O(n)
O(n) - время, необходимое на то, чтобы слить два массива длины n.
Распишем это соотношение:
T(n) = 2T(n/2) + О(n) = 4T(n/4) + 2O(n) = ... = T(1) + log(n)O(n) = O(nlog(n)).
 
Сложность алгоритма O(nlog(n))
 
Дополнительные материалы
1) Сортировка слиянием. Вики-конспекты ИТМО.

Задача

Отсортируйте данный массив, используя сортировку слиянием.


Входные данные
Первая строка входных данных содержит количество элементов в массиве NN <= 105. Далее идет N целых чисел, не превосходящих по абсолютной величине 109.


Выходные данные
Выведите эти числа в порядке неубывания.
 
Примеры
Входные данные Выходные данные
1 2
3 1
1 3




time 1200 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Mingw-w6421
Python104
Комментарий учителя