Вступление

Сортировка слиянием - один из самых известных алгоритмов сортировки. Если вы изучаете информатику, сортировка слиянием , наряду с быстрой сортировкой , вероятно, является первым эффективным универсальным алгоритмом сортировки, о котором вы слышали. Это также классический пример алгоритмов из категории « разделяй и властвуй».

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

Принцип работы сортировки слиянием:

Исходный массив делится на две примерно равные части. Если в массиве нечетное количество элементов, одна из этих «половинок» на один элемент больше другой.

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

Затем вы объединяете пары одноэлементных массивов в двухэлементные массивы, сортируя их в процессе. Затем эти отсортированные пары объединяются в четырехэлементные массивы и так далее, пока вы не получите отсортированный исходный массив.

Вот визуализация сортировки слиянием:

Как видите, тот факт, что массив не может быть разделен на равные половины, не является проблемой, тройка просто «ждет», пока не начнется сортировка.

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

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

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

Основная часть обоих этих подходов - это то, как мы объединяем (объединяем) два меньших массива в больший массив. Это делается довольно интуитивно, допустим, мы исследуем последний шаг в нашем предыдущем примере. У нас есть массивы:

• А: 2 4 7 8

• А: 1 3 11

• отсортировано: пусто

Первое, что мы делаем, это смотрим на первый элемент обоих массивов. Мы находим тот, который меньше, в нашем случае это 1 , так что это первый элемент нашего отсортированного массива, и продвигаемся вперед в массиве B:

• А: 2 4 7 8

• А: 1 3 11

• отсортировано: 1

Затем мы смотрим на следующую пару элементов 2 и 3 ; 2 меньше, поэтому мы помещаем его в отсортированный массив и перемещаемся вперед в массиве A. Конечно, мы не продвигаемся вперед в массиве B и сохраняем наш указатель на 3 для будущих сравнений:

• А: 2 4 7 8

• А: 1 3 11

• отсортировано: 1 2

Используя ту же логику, мы перебираем остальные и получаем массив из {1, 2, 3, 4, 7, 8, 11}.

Возможны два особых случая:

• Оба подмассива содержат один и тот же элемент. Мы можем перейти к любому из них и добавить элемент в отсортированный массив. Мы можем технически продвинуться вперед в обоих массивах и добавить оба элемента в отсортированный массив, но это потребует особого поведения, когда мы встретим одни и те же элементы в обоих массивах.
• У нас «заканчиваются» элементы в одном подмассиве. Например, у нас есть массив с {1, 2, 3} и массив с {9, 10, 11}. Ясно, что мы пройдемся по всем элементам в первом массиве, не продвигаясь ни разу во втором. Когда у нас заканчиваются элементы в подмассиве, мы просто добавляем элементы второго один за другим.

Имейте в виду, что мы можем сортировать как угодно - в этом примере целые числа сортируются в порядке возрастания, но мы можем так же легко сортировать в порядке убывания или сортировать настраиваемые объекты.

Выполнение

Мы будем реализовывать сортировку слиянием для двух типов коллекций - для массивов целых чисел (обычно используемых для сортировки) и для настраиваемых объектов (более практичный и реалистичный сценарий).

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

Сортировка массивов

Начнем с легкой части. Основная идея алгоритма - разделить (под) массивы на половины и рекурсивно отсортировать их. Мы хотим продолжать делать это как можно чаще, то есть до тех пор, пока не получим подмассивы, содержащие только один элемент:

 def merge_sort(array, left_index, right_index): 
 if left_index >= right_index: 
 return 
 
 middle = (left_index + right_index)//2 
 merge_sort(array, left_index, middle) 
 merge_sort(array, middle + 1, right_index) 
 merge(array, left_index, right_index, middle) 

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

Следующий шаг - это фактическая часть слияния, состоящая из нескольких шагов и сценариев:

• Создайте копии наших массивов. Первый массив - это подмассив из [left_index,..,middle] а второй из [middle+1,...,right_index]
• Мы просматриваем обе копии (отслеживая указатели в обоих массивах), выбираем меньший из двух элементов, которые мы сейчас рассматриваем, и добавляем их в наш отсортированный массив. Мы продвигаемся вперед в любом массиве, из которого мы выбрали элемент, и вперед в отсортированном массиве независимо.
• Если у нас заканчиваются элементы в одной из наших копий - просто добавьте оставшиеся элементы из другой копии в отсортированный массив.

С изложением наших требований давайте продолжим и определим функцию merge() :

 def merge(array, left_index, right_index, middle): 
 # Make copies of both arrays we're trying to merge 
 
 # The second parameter is non-inclusive, so we have to increase by 1 
 left_copy = array[left_index:middle + 1] 
 right_copy = array[middle+1:right_index+1] 
 
 # Initial values for variables that we use to keep 
 # track of where we are in each array 
 left_copy_index = 0 
 right_copy_index = 0 
 sorted_index = left_index 
 
 # Go through both copies until we run out of elements in one 
 while left_copy_index < len(left_copy) and right_copy_index < len(right_copy): 
 
 # If our left_copy has the smaller element, put it in the sorted 
 # part and then move forward in left_copy (by increasing the pointer) 
 if left_copy[left_copy_index] <= right_copy[right_copy_index]: 
 array[sorted_index] = left_copy[left_copy_index] 
 left_copy_index = left_copy_index + 1 
 # Opposite from above 
 else: 
 array[sorted_index] = right_copy[right_copy_index] 
 right_copy_index = right_copy_index + 1 
 
 # Regardless of where we got our element from 
 # move forward in the sorted part 
 sorted_index = sorted_index + 1 
 
 # We ran out of elements either in left_copy or right_copy 
 # so we will go through the remaining elements and add them 
 while left_copy_index < len(left_copy): 
 array[sorted_index] = left_copy[left_copy_index] 
 left_copy_index = left_copy_index + 1 
 sorted_index = sorted_index + 1 
 
 while right_copy_index < len(right_copy): 
 array[sorted_index] = right_copy[right_copy_index] 
 right_copy_index = right_copy_index + 1 
 sorted_index = sorted_index + 1 

Теперь давайте протестируем нашу программу:

 array = [33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26] 
 merge_sort(array, 0, len(array) -1) 
 print(array) 

И результат:

 [4, 5, 8, 9, 16, 22, 26, 29, 31, 33, 37, 42, 47, 48, 49] 

Сортировка настраиваемых объектов

Теперь, когда у нас есть базовый алгоритм, мы можем взглянуть на то, как сортировать пользовательские классы. При необходимости мы можем переопределить __eq__ , __le__ , __ge__ и другие операторы.

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

Сначала мы реализуем собственный класс Car и добавим к нему несколько полей:

 class Car: 
 def __init__(self, make, model, year): 
 self.make = make 
 self.model = model 
 self.year = year 
 
 def __str__(self): 
 return str.format("Make: {}, Model: {}, Year: {}", self.make, self.model, self.year) 

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

 def merge(array, left_index, right_index, middle, comparison_function): 
 left_copy = array[left_index:middle + 1] 
 right_copy = array[middle+1:right_index+1] 
 
 left_copy_index = 0 
 right_copy_index = 0 
 sorted_index = left_index 
 
 while left_copy_index < len(left_copy) and right_copy_index < len(right_copy): 
 
 # We use the comparison_function instead of a simple comparison operator 
 if comparison_function(left_copy[left_copy_index], right_copy[right_copy_index]): 
 array[sorted_index] = left_copy[left_copy_index] 
 left_copy_index = left_copy_index + 1 
 else: 
 array[sorted_index] = right_copy[right_copy_index] 
 right_copy_index = right_copy_index + 1 
 
 sorted_index = sorted_index + 1 
 
 while left_copy_index < len(left_copy): 
 array[sorted_index] = left_copy[left_copy_index] 
 left_copy_index = left_copy_index + 1 
 sorted_index = sorted_index + 1 
 
 while right_copy_index < len(right_copy): 
 array[sorted_index] = right_copy[right_copy_index] 
 right_copy_index = right_copy_index + 1 
 sorted_index = sorted_index + 1 
 
 
 def merge_sort(array, left_index, right_index, comparison_function): 
 if left_index >= right_index: 
 return 
 
 middle = (left_index + right_index)//2 
 merge_sort(array, left_index, middle, comparison_function) 
 merge_sort(array, middle + 1, right_index, comparison_function) 
 merge(array, left_index, right_index, middle, comparison_function) 

Давайте протестируем или изменим алгоритм на нескольких экземплярах Car

 car1 = Car("Alfa Romeo", "33 SportWagon", 1988) 
 car2 = Car("Chevrolet", "Cruze Hatchback", 2011) 
 car3 = Car("Corvette", "C6 Couple", 2004) 
 car4 = Car("Cadillac", "Seville Sedan", 1995) 
 
 array = [car1, car2, car3, car4] 
 
 merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.year < carB.year) 
 
 print("Cars sorted by year:") 
 for car in array: 
 print(car) 
 
 print() 
 merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.make < carB.make) 
 print("Cars sorted by make:") 
 for car in array: 
 print(car) 

Получаем на выходе:

 Cars sorted by year: 
 Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988 
 Make: Cadillac, Model: Seville Sedan, Year: 1995 
 Make: Corvette, Model: C6 Couple, Year: 2004 
 Make: Chevrolet, Model: Cruze Hatchback, Year: 2011 
 
 Cars sorted by make: 
 Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988 
 Make: Cadillac, Model: Seville Sedan, Year: 1995 
 Make: Chevrolet, Model: Cruze Hatchback, Year: 2011 
 Make: Corvette, Model: C6 Couple, Year: 2004 

Оптимизация

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

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

Это означает, что для данного массива, такого как {4, 8, 7, 2, 11, 1, 3} , вместо того, чтобы разбивать его на {4}, {8}, {7}, {2}, { 11}, {1}, {3} - он разделен на подмассивы, которые уже могут быть отсортированы: {4,8}, {7}, {2,11}, {1,3} , а затем их сортировка.

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

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

Однако сортировка слиянием относительно неэффективна (как по времени, так и по пространству), когда дело доходит до меньших массивов, и часто оптимизируется путем остановки, когда мы достигаем массива из ~ 7 элементов, вместо того, чтобы переходить к массивам с одним элементом и вызывать сортировку вставкой для вместо этого отсортируйте их перед объединением в более крупный массив.

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

Заключение

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

Одним из основных недостатков является дополнительная память, которую Merge Sort использует для хранения временных копий массивов перед их объединением. Тем не менее, сортировка слиянием - отличный интуитивно понятный пример, который знакомит будущих инженеров-программистов с подходом «разделяй и властвуй» при создании алгоритмов.

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