Сортировка слиянием — различия между версиями

Текущая версия на 16:48, 23 октября 2008

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

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

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

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

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

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]