Структуры и алгоритмы данных Python: сортировка слиянием

Поиск и сортировка Python: упражнение-8 с решением

Напишите программу на Python для сортировки списка элементов с использованием алгоритма сортировки слиянием.
Примечание. Согласно Википедии «Сортировка слиянием (также обычно пишется слиянием) является алгоритмом сортировки на основе сравнения O (n log n). Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода равных элементов в отсортированной выход."

Концептуально сортировка слиянием работает следующим образом:

• Разделите несортированный список на n подсписков, каждый из которых содержит 1 элемент (список из 1 элемента считается отсортированным).
• Повторно объединяйте подсписки для создания новых отсортированных подсписков, пока не останется только 1 подсписок. Это будет отсортированный список.

Пример сортировки слиянием :

Сортировка слиянием: графическое представление

Пример решения :

Код Python:

def mergeSort(nlist):
    print("Splitting ",nlist)
    if len(nlist)>1:
        mid = len(nlist)//2
        lefthalf = nlist[:mid]
        righthalf = nlist[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i=j=k=0       
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                nlist[k]=lefthalf[i]
                i=i+1
            else:
                nlist[k]=righthalf[j]
                j=j+1
            k=k+1
        while i < len(lefthalf):
            nlist[k]=lefthalf[i]
            i=i+1
            k=k+1
        while j < len(righthalf):
            nlist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",nlist)
nlist = [14,46,43,27,57,41,45,21,70]
mergeSort(nlist)
print(nlist)

Пример вывода:

 Расщепление [14, 46, 43, 27, 57, 41, 45, 21, 70]                                                               
Расщепление [14, 46, 43, 27]                                                                                   
Расщепление [14, 46]                                                                                           
Расщепление [14]                                                                                               
Слияние [14]                                                                                                 
Расщепление [46]                         
-------
Слияние [14, 21, 27, 41, 43, 45, 46, 57, 70]                                                                 
[14, 21, 27, 41, 43, 45, 46, 57, 70] 

Блок - схема:

Визуализируйте выполнение кода Python:

Следующий инструмент визуализирует, что компьютер делает шаг за шагом при выполнении указанной программы:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущая: Напишите программу на Python для сортировки списка элементов с использованием алгоритма сортировки оболочки.
Далее: Напишите программу на Python для сортировки списка элементов с использованием алгоритма быстрой сортировки.