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

Алгоритм сортировки слиянием применяется для сортировки, если есть возможность использовать для хранения промежуточных результатов память, сравнимую с размером исходного массива.

Слияние — это объединение двух или более упорядоченных массивов в один упорядоченный. Пусть требуется упорядочить массив по убыванию. Для этого сравниваются два наименьших элемента обоих массивов и наименьший из них выводится как наименьший элемент суммарного массива, затем процедура повторяется (см. процедуру «merge» в представленном ниже алгоритме). Нетрудно видеть, что слияние двух упорядоченных последовательностей A и B длин |A| и |B| происходит за O(|A|+|B|) сравнений.

Теперь рассмотрим алгоритм сортировки слиянием. Исходный массив A длины n делится пополам. Затем производится рекурсивная сортировка каждой половинки и их слияние. Пусть T(n) — число сравнений, достаточное для сортировки слиянием, тогда будет справедливо рекуррентное соотношение: \( T(n) \leq 2T(n/2)+O(n). \)

Решив это соотношение, получаем, что сложность алгоритма асимптотически оптимальна — алгоритм сортирует входной массив за время O(n log n) для любых входных данных. Однако алгоритм сортировки слиянием редко применяется на практике, так как в процессе своей работы алгоритм активно использует дополнительные массивы, что редко допустимо в реальных приложениях. <code-python> def mergesort(L):

   print funcname(),L
   if len(L) < 2: 
       return L
   return merge(mergesort(L[:len(L)/2]),mergesort(L[len(L)/2:]))

def merge(A,B):

   print funcname(),A,B,
   Out = []
   while len(A)+len(B) > 0:
       if len(B) == 0 or (len(A) > 0 and A[0] < B[0]):
           Out.append(A[0])
           A = A[1:]
       else:
           Out.append(B[0])
           B = B[1:]
   print " -> ", Out
   return Out

</code-python>

Sorting:   [3, 4, 1, 5, 9, 2, 6, 5, 3, 5]
         mergesort: [3, 4, 1, 5, 9, 2, 6, 5, 3, 5]
         mergesort: [3, 4, 1, 5, 9]
         mergesort: [3, 4]
         mergesort: [3]
         mergesort: [4]
             merge: [3] [4]  ->  [3, 4]
         mergesort: [1, 5, 9]
         mergesort: [1]
         mergesort: [5, 9]
         mergesort: [5]
         mergesort: [9]
             merge: [5] [9]  ->  [5, 9]
             merge: [1] [5, 9]  ->  [1, 5, 9]
             merge: [3, 4] [1, 5, 9]  ->  [1, 3, 4, 5, 9]
         mergesort: [2, 6, 5, 3, 5]
         mergesort: [2, 6]
         mergesort: [2]
         mergesort: [6]
             merge: [2] [6]  ->  [2, 6]
         mergesort: [5, 3, 5]
         mergesort: [5]
         mergesort: [3, 5]
         mergesort: [3]
         mergesort: [5]
             merge: [3] [5]  ->  [3, 5]
             merge: [5] [3, 5]  ->  [3, 5, 5]
             merge: [2, 6] [3, 5, 5]  ->  [2, 3, 5, 5, 6]
             merge: [1, 3, 4, 5, 9] [2, 3, 5, 5, 6]  ->  [1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
Sorted:    [1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.