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

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

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

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

Процесс однократной обработки некоторого количества данных является фазой. Самый маленький подпроцесс, который путём многократных повторений формирует всю процедуру, именуется этапом. Операция слияния подразумевает соединение пары, изначально прошедших упорядочивание подпоследовательностей, имеющих размерность N/2, в одну последовательность с размерностью n. Первые компоненты последовательностей, прошедших предварительное упорядочивание, проходят процедуру сравнения друг с другом, и в итоге определяется самый маленький. Затем нужный указатель переставляется на последующий компонент. Далее осуществляется повтор операции до момента достижения конца какой-либо подпоследовательности. Остальные компоненты другой подпоследовательности пересылаются в итоговую последовательность без всяких изменений. Пример приведён ниже:

Рисунок 1. Последовательность. Автор24 — интернет-биржа студенческих работ

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

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

Двухпутевое слияние

Алгоритм двухпутевого слияния заключается в следующем. Начальная последовательность делится на пару последовательностей:

Рисунок 2. Последовательность. Автор24 — интернет-биржа студенческих работ

Рисунок 3. Последовательность. Автор24 — интернет-биржа студенческих работ

Полученные последовательности затем проходят процесс объединения в единую последовательность, которая содержит упорядоченные пары:

Рисунок 4. Последовательность. Автор24 — интернет-биржа студенческих работ

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