Алгоритмы слияния двух неупорядоченных массивов

#алгоритм #сортировка

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

Можете подробно рассказать про алгоритм(мы) слияния массивов, либо дать короткое
четкое и понятное объяснение на эту тему, или дать ссылку на источники, где это все
подробно объясняется?
    

Ответы

Ответ 1

Во-первых, в алгоритме сортировки слиянием действительно в качестве под-алгоритма
используется алгоритм слияния двух последовательностей (массивов, списков и т.п.).
Однако слияние выполняется именно для упорядоченных последовательностей. В этом вся
суть алгоритма сортировки слиянием. Поэтому не ясно, почему в своем вопросе вы говорите
о "слиянии неупорядоченных массивов". Откуда взялись неупорядоченные массивы? И какое
это имеет отношение к сортировке слиянием?

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

В-третьих, если речь идет именно о массивах, то вышеупомянутый тривиальный алгоритм
слияния легко применим только в том случае, если мы имеем возможность на основе двух
входных массивов формировать третий (отдельный) слитый массив. Так обычно и реализуется
сортировка массивов слиянием - она требует дополнительной памяти для формирования слитых
результатов. Однако существуют эффективные алгоритмы, которые умеют сливать соседствующие
в памяти массивы прямо на месте ("in-place"), без привлечения третьего массива. Эти
алгоритмы, однако, далеко не тривиальны и, как правило, не используются в практических
реализациях сортировки слиянием.