Каскадная сортировка

При рассмотрении каскадной сортировки или сортировки методом касадного слияния следует отметить, что данный метод относится к внешней улучшенной сортировке, не простым слиянием .

Каскадное слияние объединяет два списка отсортированных данных за один раз, пока не останется только один отсортированный список, и используется для сортировки в памяти, поскольку оно более эффективно, чем K-way merge. Мы стремимся к тому, чтобы наша реализация имела высокую производительность в памяти, которая плавно снижается по мере превышения лимита доступной памяти.

При каскадной сортировке мы объединяем два блока отсортированных данных за один раз, пока не останется только один отсортированный блок. Естественно, мы хотим использовать все доступные потоки для вычисления слияния. Если у нас гораздо больше отсортированных блоков, чем потоков, мы можем назначить каждый поток для слияния двух блоков. Однако по мере слияния блоков у нас не будет достаточно блоков, чтобы все потоки были заняты. Это особенно медленно, когда объединяются последние два блока: Один поток должен обработать все данные.

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

Простой прием для уменьшения ввода-вывода - это зигзагообразное перемещение по парам блоков для слияния в каскадной сортировке слиянием. Это показано на рисунке ниже (пунктирные стрелки указывают, в каком порядке объединяются блоки).

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

При применении различных методов сортировки также стоит не забывать о временных рамках выполения алгоритма. Временная сложность алгоритма определяется количеством входных данных. Для простоты входные данные представляются параметром n. Этот параметр пропорционален величине обрабатываемого набора данных и может обозначать:

•        размер массива или файла при сортировке или поиске;

•        степень полинома;

•        количество символов в строке;

1.4 Принципы программирования сортировки данных.

Программирование сортировки данных может быть выполнено на различных языках. Наиболее популярным до сих пор остается язык C для системного программирования и C++. Пример такой сортировки приведен в приложении 1 к данной работе. При запуске этого программного кода на локальной машине он создает образец входного файла "input.txt" с 10000 случайными числами. Он сортирует числа и помещает отсортированные числа в файл "output.txt". Он также генерирует файлы с именами 1, 2, ... для хранения отсортированных прогонов.