Алгоритмы сортировки

В этой статье речь пойдет о сравнении некоторых алгоритмов сортировки, реализованных на C++ для последовательности не упакованных BCD чисел большого размера.



Данный анализ я проводил в качестве летней практики в компании «Программные технологии».
Сортируемая последовательность не имеет заголовка, числа в ней имеют различную разрядность и хранятся без выравнивания. Между числами стоят разделители (0xFF).

Для осуществления сортировки с помощью библиотечной функции вводится дополнительный уровень данных – контейнер, содержащий указатели на области памяти, каждая из которых содержит одно BCD число. В сравнении участвуют:

1. Сортировка слиянием;
2. Сортировка слиянием без использования буфера;
3. Естественная сортировка слиянием;
4. Естественная сортировка слиянием без использования буфера;
5. Модифицированная естественная сортировка слиянием;
6. Модифицированная естественная сортировка слиянием без использования буфера;
7. std::sort.