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

Merge sort - рекурсивный алгоритм сортировки, разбивающий основной массив на подмассивы, сортирующий их и собирающий всё обратно в отсортированном виде. Такие алгоритмы называются "разделяй и властвуй", но о таких алгоритмах попозже. (в курсе такого не будет=) )

Алгоритм

Алгоритм Merge sort на подмасиве $array[l\dots r]$ выглядит следующем образом:

1. Если l = r, ничего не делать, так как массив отсортирован.
2. Вычислить середину отрезка: $m=(l+r)/2$ с округлением вниз.
3. Рекурсивно отсортировать $array[l\dots m]$.
4. Рекурсивно отсортировать $array[m+1\dots r]$.
5. Объединить (merge) два уже отсортированных массива $array[l\dots m]$ и $array[m+1\dots r]$ в один общий отсортированный массив $array[l\dots r]$

Объединение отсортированных массивов

Пункт (5) является очень простым. Используя метод двух указателей, можно двигать границы $i$ и $j$ добавляя в итоговый массив $array[l\dots r]$ самый маленький из $array[i]$ и $array[j]$.

Преимущества алгоритма

1. Стабильный алгоритм
2. Сложность алгоритма в худшем случае — $O(n\log n)$ , следовательно, он идеален для больших массивов.
3. Алгоритм параллелен — его можно спокойно ускорить, разбив действия на разные потоки процессора.

Недостатки алгоритма

1. Требователен к памяти.
2. Не всегда оптимален для маленьких массивов.

Реализация алгоритма

Я специально оставлю реализацию на подумать (я проверил на задаче, она работает). (реализация взята отсюда)

void mergeSort(int* a, int* tmp, int l, int r) {
  if (l == r) return;       // (1)
  int m = l + (r - l) / 2;  // (2)
  mergeSort(a, tmp, l, m);  // (3) рекурсивный запуск для левой части
  mergeSort(a, tmp, m + 1, r);  // (4) рекурсивный запуск для правой части
  for (int i = l; i <= r; i++)
    tmp[i] = a[i];  // массив tmp равен а (соответствующие подотрезки)
  // (5) два указателя, очень красивые
  int ai = l, bi = m + 1;
  for (int i = l; i <= r; i++) {
    if (bi > r || ai <= m && tmp[ai] <= tmp[bi])
      a[i] = tmp[ai++];
    else
      a[i] = tmp[bi++];
  }
}

Запуск функции сортировки int *tmp = new int[size]; mergeSort(arr, tmp, 0, size-1);.

Можно написать без использование глобального массива tmp.

Доказательство сложности алгоритма

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Это на любом сайте написано. Думайте.

Давайте объясню на пальцах :

Во время разбиения массива на две части, каждый элемент массива обрабатывается один раз. Всего уровней рекурсии будет $\log n$, так как каждый раз массив делится пополам. При слиянии двух частей массива для всего уровня выполняется $O(n)$ операций.

Ввод

49 12 -3 15

Работа алгоритма

1. Разбиение массива { 49 12 -3 15 } на два подмассива { 49 12 } и { -3 15 }
2. Разбиение подмассивов на части { 49 } и { 12 }, { -3 } и { 15 }
3. Сборка отсортированных подмассивов: { 12 49 } и { -3 15 }
4. Сборка массива из подмассивов: { -3 12 15 49 }

Вывод

-3 12 15 49

Можно решить задачу о количестве инверсий в массиве. TODO?

¹ : можно реализовать, но это слишком сложно.