Сортировка слиянием - достижение максимального эффекта

Этот вид сортировки отлично описан на многих сайтах Рунета.

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

Как же тут не вспомнить про быструю, рекурсивную сортировку.
В том алгоритме все наоборот.
Очень быстро сортируются сравнительно малые массивы (равномерно перемешанные), а в случае очень больших массивов (особенно если определенная часть уже отсортирована) может происходить рекурсивное переполнение стека.

Вывод: сортировку слиянием следует совмещать с быстрой сортировкой.

Не дробить начальный массив до элемента, а лишь до величины заданной константой MIN_CHUNK_SIZE и эти куски сортировать быстрой сортировкой, ну, а объединять потом, конечно, слиянием. 



ПРИМЕРЫ:

VBA Excel
Объединение в одном алгоритме сортировки, дополняющих друг друга алгоритмов Хоара и слияния…

C++ Visual Studio 2008
Быстрое слияние двух упорядоченных массивов в один с сохранением того же порядка сортировки…

C# Visual Studio 2010 .NET Framework 4
Сортировка слиянием массива записей (структур)


Другие примеры на языках «C»,«C++»,«C#»

Другие примеры на языке «Visual Basic for application - VBA»


Поделиться в соц сетях:




Если на этой странице не нашлось того, что Вы так искали...

         Не расстраивайтесь, не все потеряно... Смело щелкайте...

Сайт помощи студентам по программированию и информатике

Program code