Сортировка слиянием. Поразрядная сортировка

Слияние является процессом объединения двух и более отсортированных файлов в некоторый третий отсортированный файл [3]. Мы можем использовать такой подход к сортировке файла следующим образом. Разделим файл на n подфайлов размером 1 и будем объединять соседние (необъединенные) пары файлов. Тогда будем иметь примерно n/2 файлов размером 2. Повторяем этот процесс до тех пор, пока не останется только один файл размером n. Рассмотрим сказанное на примере.

Первоначальный файл (25) (57) (48) (37) (12) (92) (86) (33)

Просмотр 1 (25, 57) (37, 48) (12, 92) (33, 86)

Просмотр 2 (25, 37, 48, 57) (12, 33, 86, 92)

Просмотр 3 (12, 25, 33, 37, 48, 57, 86, 92)

Поразрядная сортировка

Этот метод основан на свойстве значений действительных чисел в позиционном представлении сортируемых чисел. Для простоты предполагаем, что все числа имеют одинаковое число цифр, что при необходимости выполняется добавлением незначащих нулей. Предположим, что мы выполняем следующие действия над файлом для каждой цифры, начиная с самой младшей цифры и кончая самой старшей цифрой. Берем каждое число в том порядке, в котором оно появляется в файле, и помещаем его в одну из 10 очередей в зависимости от значения цифры, которая в данный момент обрабатывается. Затем восстанавливаем каждую очередь к виду первоначального файла, начиная с очереди чисел с цифрой 0 и кончая очередью чисел с цифрой 9. Когда эти действия будут выполнены для каждой цифры, начиная с самой младшей и кончая самой старшей, данный файл будет отсортирован. Рассмотрим изложенную процедуру на примере.

Первоначальный файл 25 57 48 37 12 92 86 33

Очереди, организованные по МЗЦ (младшей значащей цифре)

После первого просмотра: 12 92 33 25 86 57 37 48

Очереди, организованные по СЗЦ (старшей значащей цифре)

Отсортированный файл 12 25 33 37 48 57 86 92

Временные затраты на метод поразрядной сортировки зависят от числа цифр (m) и числа элементов в файле (n). Для того, чтобы сэкономить значительный объем работы при обработке очередей, рекомендуется использовать связанное распределение данных на основе указателей.