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

Как и быстрая сортировка, сортировка слиянием (mergesort) — это рекурсивный алгоритм. Он также разделяет список на два подсписка, и рекурсивно сортирует подсписки.

Сортировка слиянием делит список пополам, формируя два подсписка одинакового размера. Затем подсписки рекурсивно сортируются, и отсортированные подсписки сливаются, образуя полностью отсортированный список.

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

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

Public Sub Mergesort(List() As Long, Scratch() As Long, _

ByVal min As Long, ByVal max As Long)

Dim middle As Long

Dim i1 As Long

Dim i2 As Long

Dim i3 As Long

‘ Если в списке больше, чем CutOff элементов,

‘ завершить его сортировку процедурой SelectionSort.

If max - min < CutOff Then

Selectionsort List(), min, max

Exit Sub

End If

‘ Рекурсивная сортировка подсписков.

middle = max \ 2 + min \ 2

Mergesort List(), Scratch(), min, middle

Mergesort List(), Scratch(), middle + 1, max

‘ Слить отсортированные списки.

i1 = min ‘ Индекс списка 1.

i2 = middle + 1 ‘ Индекс списка 2.

i3 = min ‘ Индекс объединенного списка.

Do While i1 <= middle And i2 <= max

If List(i1) <= List(i2) Then

Scratch(i3) = List(i1)

i1 = i1 + 1

Else

Scratch(i3) = List(i2)

i2 = i2 + 1

end If

i3 = i3 + 1

Loop

‘ Очистка непустого списка.

Do While i1 <= middle

Scratch(i3) = List(i1)

i1 = i1 + 1

i3 = i3 + 1

Loop

Do While i2 <= max

Scratch(i3) = List(i2)

i2 = i2 + 1

i3 = i3 + 1

Loop

‘ Поместить отсортированный список на место исходного.

For i3 = min To max

List(i3) = Scratch(i3)

Next i3

End Sub

Сортировка слиянием тратит много времени на копирование временного массива на место первоначального. Программа FastSort использует функцию API MemCopy, чтобы немного ускорить эту операцию.

Даже с использованием функции MemCopy, сортировка слиянием немного медленнее, чем быстрая сортировка. В нашем тесте на компьютере с процессором Pentium с тактовой частотой 90 МГц, сортировка слиянием потребовала 2,95 сек для упорядочения 30.000 элементов со значениями в диапазоне от 1 до 10.000. Быстрая сортировка потребовала всего 2,44 сек.

Преимущество сортировки слиянием в том, что время ее выполнения остается одинаковым независимо от различных распределений и начального расположения данных. Быстрая же сортировка дает производительность порядка O(N²) и достигает глубокого уровня вложенности рекурсии, если список содержит много одинаковых значений. Если список большой, быстрая сортировка может переполнить стек и привести к аварийному завершению работы программы. Сортировка слиянием никогда не достигает слишком глубокого уровня вложенности рекурсии, т.к. всегда делит список на равные части. Для списка из N элементов, глубина вложенности рекурсии для сортировки слиянием составляет всего лишь log(N).

В другом тесте, в котором использовались 30.000 элементов со значениями от 1 до 100, сортировка слиянием потребовала столько же времени, сколько и для элементов со значениями от 1 до 10.000 — 2,95 секунд. Быстрая сортировка заняла 15,82 секунды. Если значения лежали между 1 и 50, сортировка слиянием потребовала 2,95 секунд, тогда как быстрая сортировка — 138,52 секунды.