При внимательном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно обратить внимание, что многие методы основаны на применении одной и той же базовой операции "Сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки.
// базовая операция сортировки if ( A[i] > A[j] ) { temp = A[i]; A[i] = A[j]; A[j] = temp; }
Целенаправленное применение данной операции позволяет упорядочить данные; в способах выбора пар значений для сравнения собственно и проявляется различие алгоритмов сортировки.
Рассмотренная выше базовая операция сортировки может быть надлежащим образом обобщена для случая, когда упорядочиваемые данные разделены на p, p > 1, частей (блоков). Выделяемые при этом блоки имеют, как правило, одинаковый размер, и содержат в этом случае n/p элементов.
Блоки обычно упорядочиваются в самом начале сортировки - как можно заметить, блоки могут упорядочиваться независимо друг от друга, т.е. параллельно. Далее, следуя схеме одноэлементного сравнения, упорядочение содержимого блоков Ai и Ai+1 может быть осуществлено следующим образом:
Рассмотренная процедура обычно именуется в литературе как операция "Сравнить и разделить" (compare-split).