Учебники

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

В этой главе мы обсудим сортировку слиянием и проанализируем ее сложность.

Постановка задачи

Проблема сортировки списка чисел сразу поддается стратегии «разделяй и властвуй»: разбейте список на две половины, рекурсивно сортируйте каждую половину, а затем объедините два отсортированных подсписка.

Решение

В этом алгоритме числа хранятся в массиве numbers [] . Здесь p и q представляют начальный и конечный индексы подмассива.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r) 

Function: Merge (numbers[], p, q, r)
n 1 = q – p + 1 
n 2 = r – q 
declare leftnums[1…n 1 + 1] and rightnums[1…n 2 + 1] temporary arrays 
for i = 1 to n 1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n 2 
   rightnums[j] = numbers[q+ j] 
leftnums[n 1 + 1] = ∞ 
rightnums[n 2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1 

Анализ

Рассмотрим время выполнения Merge-Sort как T (n) . Следовательно,

T (n) = \ begin {case} c & if \: n \ leqslant 1 \\ 2 \: x \: T (\ frac {n} {2}) + d \: x \: n & в противном случае \ end {case} , где c и d – константы

Следовательно, используя это рекуррентное соотношение,

T (n) = 2 ^ i T (\ frac {n} {2 ^ i}) + idn

As, i = log \: n, \: T (n) = 2 ^ {log \: n} T (\ frac {n} {2 ^ {log \: n}}) + log \: ndn

= \: cn + dnlog \: n

Следовательно, T (n) = O (n \: log \: n)

пример

В следующем примере мы продемонстрировали алгоритм Merge-Sort шаг за шагом. Во-первых, каждый итерационный массив делится на два вложенных массива, пока этот массив не содержит только один элемент. Когда эти подмассивы не могут быть разделены далее, выполняются операции слияния.