Руководство по сортировке слиянием на Python

Сортировка данных – одна из наиболее распространенных операций, которую выполняют практики данных в своей повседневной работе. Многократно нам нужно отображать данные в определенном порядке, чтобы извлечь значимую информацию. К счастью, сегодня мы не обязаны делать это вручную. Компьютеры могут сделать это волшебство за нас с непревзойденной производительностью.

Существует несколько стратегий сортировки данных. В этом учебнике мы проанализируем одну из наиболее эффективных техник сортировки. Алгоритм “сортировки слиянием” использует стратегию “разделяй и властвуй” для сортировки неупорядоченного массива, сначала разбивая его на более мелкие массивы, которые затем объединяются в правильном порядке.

В следующих разделах мы обсудим все детали алгоритма сортировки слиянием, как он выглядит в Python, и некоторые практические советы для плавной реализации.

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

Существует множество алгоритмов сортировки, но трудно найти тот, который работает лучше сортировки слиянием. Неудивительно, что этот алгоритм используется во всех видах прикладных приложений, таких как сортировка больших баз данных или организация файлов на обычном компьютере.

Алгоритм основан на парадигме “разделяй и властвуй”, которую можно разбить на три части:

• Разделение: этот процесс разделяет проблему на более мелкие подзадачи.
• Покорение: подзадачи решаются рекурсивно.
• Объединение: решения подзадач объединяются для достижения конечного решения.

Стратегия разделяй и властвуй

Давайте посмотрим, как работает сортировка слиянием. Предположим, что мы хотим упорядочить следующие числа, применяя алгоритм сортировки слиянием. Алгоритм рекурсивно делит данные на две части и продолжает деление, пока каждый список не будет содержать один элемент. Затем мы объединяем их, сортируя в другой список.

Задача сортировки слиянием. Источник: DataCamp

Временная и пространственная сложность сортировки слиянием

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

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

Временная сложность сортировки слиянием

Как мы объяснили в отдельном руководстве по Нотации большого O и сложности по времени, цель анализа сложности по времени не заключается в прогнозировании точного времени выполнения алгоритма, а скорее в оценке того, насколько эффективен алгоритм путем анализа изменения его времени выполнения по мере увеличения объема входных данных.

Анализ сложности по времени записывается в нотации большого O, математической нотации, описывающей темп роста или убывания функции. Сортировка слиянием имеет логарифмическую или линеарифмическую сложность по времени, обозначаемую как O(N log(N)), где N – количество элементов в списке. Буква ‘O’ означает ‘порядок’ роста. 

В анализе сложности по времени сложность линеарифмического порядка ведет себя приблизительно так же, как линейная сложность, что означает, что время выполнения будет прямо пропорционально объему данных. Таким образом, если объем данных удваивается, время, необходимое для обработки данных, также должно удвоиться, т. е. количество разделений и слияний удвоится.

Поскольку сложность по времени сортировки слиянием ведет себя линейно, ее сложность остается одинаковой как для лучшего, среднего, так и для худшего случаев. Это означает, что независимо от порядка ввода, алгоритм всегда будет выполнять одинаковое количество шагов для завершения.

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

Наконец, помимо времени, необходимого для завершения задачи, еще одним важным аспектом при анализе сложности алгоритма является оценка того, сколько памяти потребуется алгоритму для завершения по мере увеличения размера проблемы.

Это покрывается концепциями сложности пространства и вспомогательного пространства. Последнее относится к дополнительному пространству или временному пространству, используемому алгоритмом, в то время как первое относится к общему пространству, занимаемому алгоритмом относительно размера ввода. Другими словами, сложность пространства включает как вспомогательное пространство, так и пространство, используемое вводом.

Сортировка слиянием имеет сложность пространства O(N). Это потому, что она использует вспомогательный массив размером N для слияния отсортированных половин входного массива. Вспомогательный массив используется для хранения объединенного результата, а входной массив перезаписывается отсортированным результатом.

Реализация сортировки слиянием на Python

Давайте реализуем алгоритм сортировки слиянием на Python. Существует несколько способов написания кода для алгоритма; однако мы придерживаемся того, который основан на рекурсии, который, пожалуй, является самым простым для понимания и требует меньше строк кода, чем другие альтернативы, основанные на итерации.

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

Если вы новичок в этой теме, в программировании рекурсия происходит, когда функция вызывает саму себя. Вы можете ознакомиться с нашим Учебником по Пониманию Рекурсивных Функций на Python, чтобы узнать все о этих мощных функциях.

Для реализации сортировки слиянием сначала мы определяем базовый случай: если список содержит только один элемент, он уже отсортирован, поэтому мы немедленно возвращаемся. В противном случае мы разделяем список на две половины, left_half и right_half, и вызываем merge_sort() рекурсивно для каждой из них. Этот процесс продолжается до тех пор, пока все подсписки не содержат по одному элементу.

После того, как у нас есть эти отсортированные подсписки, мы начинаем процесс слияния. Для этого мы инициализируем три индексных переменных: i для отслеживания позиции в left_half, j для right_half и k для окончательно объединенного списка. Затем мы сравниваем элементы из обеих половин. Если текущий элемент в left_half меньше, мы помещаем его в my_list[k] и перемещаем i вперед. В противном случае мы берем элемент из right_half, помещаем его в my_list[k] и увеличиваем j. После каждого сравнения мы перемещаем k вперед к следующей позиции в итоговом списке.

Этот процесс продолжается до тех пор, пока мы не сравним все элементы в одной из половин. Если в left_half или right_half остались элементы, мы добавляем их напрямую в окончательный список, гарантируя, что никакие данные не останутся позади. Поскольку сортировка слиянием работает рекурсивно, этот процесс слияния выполняется на каждом уровне рекурсии до тех пор, пока весь список не будет отсортирован.

Реализация на Python

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

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge Sort против других алгоритмов сортировки

Merge sort – довольно быстрый алгоритм сортировки, особенно подходящий для больших баз данных, и часто используется в качестве ориентира для других алгоритмов. Однако, когда речь идет о более коротких списках, его производительность обычно ниже, чем у других алгоритмов сортировки.

В следующей таблице вы можете найти сравнение сортировки слиянием с другими популярными алгоритмами сортировки.

Практические применения сортировки слиянием

Сортировка слиянием имеет высокую производительность при сортировке больших списков, но ее эффективность снижается при работе с меньшими списками. Также она может быть менее эффективной в ситуациях, где входные списки уже имеют определенную степень упорядоченности, поскольку сортировка слиянием будет выполнять те же самые шаги независимо от порядка в списке.

Отличный случай использования сортировки слиянием – это связанные списки. Связанный список – это структура данных, которая состоит из узлов, линейно связанных друг с другом. Каждый узел содержит данные и ссылку для соединения с следующим узлом.

Сортировка слиянием предпочтительна для связанных списков, потому что она требует только последовательного доступа к данным, что хорошо сочетается с природой связанных списков. Кроме того, сортировка слиянием является стабильным алгоритмом сортировки (т.е. она сохраняет относительный порядок равных элементов в отсортированном выводе), что является очень важным обстоятельством для сохранения порядка связанных списков.

Общие ошибки и устранение неполадок

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

Мы уже установили, что сортировка слиянием работает лучше с большими наборами данных. Для меньших наборов данных другие алгоритмы сортировки с временной сложностью O(N^2), например, сортировка вставками, могут быть более эффективными. В этом случае вам просто нужно создать пороговое значение размера, ниже которого вы будете использовать алгоритм сортировки вставками вместо слияния и сортировки.

Кроме того, хорошей идеей для исследования было бы параллелизация. Шаги сортировки слиянием могут быть легко параллелизованы с правильной вычислительной мощностью, тем самым сокращая время завершения. Прочтите наше руководство CPU против GPU, чтобы узнать больше о параллельных вычислениях.

Заключение

Сортировка слиянием – один из самых эффективных и популярных алгоритмов сортировки, но в замечательной и всё более расширяющейся вселенной алгоритмов есть ещё многое, что можно изучить. Если вас интересует техническая сторона алгоритмов, их работа, а также связанная с ними сложность, достоинства и недостатки, эти ресурсы DataCamp могут помочь вам продолжить обучение:

• Курс “Введение в структуры данных и алгоритмы”
• Трек навыков программирования на Python
• Трек основ данных на Python
• Курс “Продвинутый Python”
• Трек карьеры “Аналитик данных на Python”
• Большая О-нотация и вычислительная сложность по времени