Verfahren

Ein Feld wird in mehrere (gleichgroße) Teilfelder geteilt. Diese werden mit einem "normalen" Sortieralgorithmus (sort1) getrennt voneinander sortiert. Anschließend werden die sortierten Teilfelder als Elemente betrachtet und mit einem beliebigen zweiten Sortieralgorithmus (sort2) sortiert, bei dem die compare_exchange-Operationen durch merge_split-Operationen ersetzt wurden.

In der Regel wird als sort1 ein schelles sequentielles Sortierverfahren (z.B. Quicksort) und als sort2 ein schnelles paralleles Sortierverfahren (z.B. Oetsort) verwendet.