Алгоритм сортировки слиянием

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

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

Вот наглядная демонстрация работы алгоритма сортировки слиянием:

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

Концептуальный обзор

В нашем примере у нас есть список, содержащий 6 номеров, и мы собираемся разделить его на 2 подсписка. Способ, которым мы разделили бы его в коде, таков: мы берем первый индекс [0], добавляем его к последнему индексу [5], делим сумму на 2 и округляем результат в меньшую сторону. Середина массива находится в индексе 2. Как показано на рисунке выше, теперь у нас есть 2 подсписка [3, 11, 8] и [18, 4, 25]. Затем мы собираемся рекурсивно применить алгоритм сортировки слиянием к этим подмассивам.

Начнем с левого подмассива [3, 11, 8]. Делим его пополам и получаем [3, 11] и [2]. Поскольку мы используем рекурсивный алгоритм, мы собираемся погрузиться полностью влево, добраться до базового случая, а затем перейти к правому подмассиву. Теперь мы переходим к подмассиву [3, 11] и далее делим его на два подмассива длиной в один. Как только мы достигли подмассивов длины один, здесь происходит вторая часть сортировки слиянием.

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

Мы начинаем сравнивать 2 числа (2 подмассива длины один), и тот, который меньше, идет первым, а тот, который больше, идет вторым. Теперь у нас есть отсортированный массив [3,11] синего цвета. Второй синий подмассив [8] уже отсортирован.

Теперь у нас есть 2 подмассива, которые, как мы знаем, отсортированы. И теперь мы создаем новый массив, где мы рекомбинируем их, но мы удостоверяемся, что этот 4-элементный подмассив отсортирован. Как мы это делаем? Сравниваем первые элементы каждого подмассива 3 и 8.

3 меньше 8, поэтому, когда мы создаем новый подмассив, мы сначала добавляем 3, перемещаем указатель на 11 и сравниваем 11 и 8. 8 меньше 11, поэтому затем мы добавляем 8 к рекомбинированному массиву. Наконец, мы добавляем 11, и все готово — у нас есть рекомбинированный подмассив из 3 элементов, который отсортирован [3, 8, 11].

Теперь мы возвращаемся к нашему правому подмассиву [18, 4, 25] и выполняем те же действия с этим подмассивом. Сначала мы разделим правый подмассив так же, как мы разделили левый подмассив, мы разделим его на подмассивы, состоящие из одного элемента. [18], [4] и [25]. Затем мы сортируем и рекомбинируем их в отсортированный массив [4, 18, 25] точно так же, как мы делали с левым подмассивом.

Мы почти на месте! Снова взглянув на наш график, теперь, когда у нас есть два отсортированных подмассива длины 3 каждый [3, 8, 11] и [4, 18, 25], мы можем объединить их в один окончательный отсортированный массив. У нас будет 2 указателя, установленных на первый элемент в каждом подмассиве. Мы строим массив, длина которого будет равна длине нашего входного массива.

Мы сравниваем 3 с 4, 3 меньше 4, поэтому 3 прибавляется первым.

Мы перемещаем указатель левого подмассива вправо. 8 больше 4. Мы знаем, что каждое число в левом подмассиве после 8 больше 8, потому что оно отсортировано, и та же логика применима к правому подмассиву — любое число после 4 больше, чем 8. 4. Итак, 4 — это наше следующее наименьшее число, которое добавляется к окончательному отсортированному массиву.

Мы перемещаем правый указатель подмассива вправо. 18 больше 8, поэтому мы прибавляем 8.

Мы перемещаем указатель на 11. 11 меньше, чем 18, и мы добавляем 11 рядом.

Мы перемещаем указатель вправо, и теперь мы закончили с левым подмассивом. Мы знаем, что любые оставшиеся числа в правом подмассиве будут добавлены в том порядке, в котором они были, потому что правый подмассив отсортирован, поэтому мы добавляем 18 и 25. Теперь у нас есть окончательный отсортированный массив.

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

Давайте теперь проведем анализ сложности.

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

При первом обращении к входному массиву длины n мы делим его пополам. Создание копии — это операция O(n), а объединение подмассивов — также операция O(n). Итак, у нас есть O(2n), мы отбрасываем константу и получаем O(n).

Рекурсивные вызовы двух подмассивов — это O (n), разделение подмассивов — O (n/2), слияние — O (n/2), и мы опускаем константы, поэтому O (n).

При следующем вызове у нас есть четыре подмассива O(n/4) + O(n/4) + O(n/4) + O(n/4), мы опускаем константы, поэтому O(n).

Как мы видим, каждый уровень займет O(n) времени. Здесь в игру вступает O(log n). Поскольку мы делим каждый массив пополам, а затем делим их пополам, а затем делим их пополам, мы получаем временную сложность O (n log n). Для дальнейшего пояснения, алгоритм сортировки слиянием делит входные данные пополам, пока не будет достигнут список из одного элемента, для чего требуется log n уровней разделения. На каждом уровне алгоритм выполняет n сравнений, выбирая и копируя элементы из левого и правого разделов, что дает n * log n сравнений.

Космическая сложность

Сортировка слиянием требует O(n) дополнительных элементов памяти для временного массива объединенных элементов. Для окончательной операции слияния временный список содержит то же количество элементов, что и входные данные. Некоторые алгоритмы сортировки сортируют элементы списка на месте и не требуют дополнительной памяти.

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

def msort(arr, start, end):
    # Leaf node, condition to end recursion
    if start >= end:
        return
    
    # Internal node worker
    mid = (start + end) // 2 #we find a mid point to split the array into two halves
    msort(arr, start, mid)   #sorting the 1st haf recursively
    msort(arr, mid + 1, end) #sorting the 2nd haf recursively
    
    
    # Merge the two sorted halves
    i = start   # index to iterate over the firstr half
    j = mid + 1 # index to iterate over the second half
    mlist = [] #temporary array to put sorted elements
    
    """
    we are comparing values of index i and j in the sub arrays
    if the value at index i is smaller or equal to the value at index j
    we append this the smaller value to the temp array mlist
    otherwise, we add the value at index j to the temp array mlist
    then we keep moving the idex of i and j until the end of each sub array
    
    """
    
    while i <= mid and j <= end:
        if arr[i] <= arr[j]:
            mlist.append(arr[i])
            i += 1
        elif arr[j] < arr[i]:
            mlist.append(arr[j])
            j += 1
    
    # Gather phase        
    while i <= mid:
        mlist.append(arr[i])
        i += 1
    while j <= end:
        mlist.append(arr[j])
        j += 1
    
    # Store in original array
    arr[start:end + 1] = mlist

def merge_sort(arr):
    msort(arr, 0, len(arr) - 1)
    return arr

Заключение

Сортировка слиянием является примером алгоритма «разделяй и властвуй». Он рекурсивно разбивает проблему на две или более связанных подзадач, пока они не станут достаточно простыми, чтобы их можно было легко решить. Мы разбивали список на подсписки до тех пор, пока в каждом подсписке не было только одного элемента, что упростило решение, поскольку список с одним элементом сортируется по определению. Время выполнения сортировки слиянием составляет O(n * log n), потому что, хотя разбиение исходного списка на подсписки является логарифмическим, алгоритму требуется линейное время для обработки каждого элемента в подсписках по мере их слияния. С логарифмически линейной временной сложностью сортировка слиянием является одним из наиболее эффективных алгоритмов сортировки и широко используется учеными-компьютерщиками.

Изучите другие распространенные алгоритмы сортировки:

• Пузырьковая сортировка
• Сортировка вставками
• Сортировка выбором
• Быстрая сортировка