Сортировка является одной из типовых проблем обработки данных и обычно понимается как задача размещения элементов неупорядоченного набора значений
S={a0, a1, …, an-1}
в порядке монотонного возрастания или убыванияS={(a0, a1, …, an-1): a0<=a1<=a2<= …<= an-1}
(здесь и далее все пояснения для краткости будут даваться только на примере упорядочивания данных по возрастанию).
Возможные способы решения этой задачи широко обсуждаются в литературе; один из наиболее полных обзоров алгоритмов сортировки содержится в работе Кнута (2000) , может быть рекомендована также работа Кормена, Лейзерсона и Ривеста (1999).
Вычислительная трудоемкость процедуры упорядочивания является достаточно высокой. Так, для ряда известных простых методов (пузырьковая сортировка, сортировка включением и др.) количество необходимых операций определяется квадратичной зависимостью от числа упорядочиваемых данных
T ~ n2.
Для более эффективных алгоритмов (сортировка слиянием, сортировка Шелла, быстрая сортировка) трудоемкость определяется величиной
T ~ n log2 n.
Данное выражение дает также нижнюю оценку необходимого количества операций для упорядочивания набора из n значений; алгоритмы с меньшей трудоемкостью могут быть получены только для частных вариантов задачи.
Ускорение сортировки может быть обеспечено при использовании нескольких (p > 1) вычислительных элементов (процессоров или ядер). Исходный упорядочиваемый набор в этом случае «разделяется» на блоки; которые могут обрабатываться вычислительными элементами параллельно.
Оставляя подробный анализ проблемы сортировки для отдельного рассмотрения, здесь основное внимание мы уделим изучению параллельных способов выполнения для ряда широко известных методов внутренней сортировки, когда все упорядочиваемые данные могут быть размещены полностью в оперативной памяти ЭВМ.