На каждой фазе алгоритма быстрой сортировки выбирается сводная точка, и данные делятся на две части ниже и ниже сводной точки (и некоторый разрыв связи для его совпадения).
Теперь каждый поворот требует передачи данных.Кроме того, дисперсия относительного положения центра вокруг того, чтобы быть срединным элементом, довольно высока.Вместо этого можно было бы взять выборку из k элементов, iid и разделить данные на k + 1 части, используя образцы элементов в качестве границ для различных частей.И хотя некоторые части могут быть слишком маленькими или слишком большими, большинство должно быть в порядке;а остальным потребуется некоторая коррекция (например, путем подсчета), но это должно быть выполнимо.
Я не пробовал такой подход над (двоичной) быстрой сортировкой, но мне было интересно, если такой подход используется впрактиковаться вообще, и если это действительно выгодно.
PS - Если вы можете сказать что-нибудь о пригодности к распараллеливанию (используя AVX-512 на CPU, с Xeon Phi, с GPU и т. д.) - это было бы очень полезно.