Просмотр исходного текста страницы Сортировка слиянием

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

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

Теперь рассмотрим алгоритм сортировки слиянием. Исходный массив ''A'' длины ''n'' делится пополам.  
Затем производится рекурсивная сортировка каждой половинки и их слияние. 
Пусть ''T(n)'' — число сравнений, достаточное для сортировки слиянием, тогда будет справедливо
рекуррентное соотношение:
<m>
  T(n) \leq 2T(n/2)+O(n).
</m>
  
Решив это соотношение, получаем, что сложность алгоритма асимптотически оптимальна — алгоритм сортирует входной массив за время ''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]



[[Category:Алгоритмы]]
{{replicate-from-custiswiki-to-lib}}