Простая сортировка массива очень простая задача, в то время как эффективная сортировка очень сложная, во многом из-за простоты задачи.

Смысл этого логического парадокса заключается в том, что решение сложной задачи возможно множеством способов, среди которых всегда можно попробовать найти еще более эффективный. В то время как решение простой задачи, обычно возможно всего несколько способами, усовершенствовать которые не так просто, по причине того, что за десятки лет работы множества людей оптимизация достигла поистине впечатляющего уровня.

Наиболее очевидным путем оптимизации сортировки массива является параллельная сортировка его частей, но этот способ сталкивается с проблемой высоких накладных расходов на запуск параллельных процессов и несоизмеримой сложностью решения проблемы и получаемого результата. Как следствие представляется очень интересным способ задействовать для сортировки возможности SIMD инструкций, которые даже для «стандартного» SSE2 теоретически могут позволить сортировать 4-е потока 32-х битных чисел и добиться четырёхкратного прироста скорости.

Ниже представлен вариант сортировки массива из 16-и, 32-х битных безнаковых чисел, реализованный посредством SIMD инструкций SSE4.1 сета. Представленный код по своей сути является демонстратором алгоритма и не подразумевает практического применения.

Возражения что массивы редко бывают четко фиксированной длины, я хотел бы парировать замечанием, что большие массивы можно разделить на субмассивы требуемой длины, алгоритм может быть легко расширен до 32-х и 64-х членов, а массивы не кратной длины могут быть легко дополнены «избыточными» элементами имеющими максимально/минимальное значение, которые как следствие в ходе сортировки сосредоточатся на каком либо из концов массива где их можно будет легко проигнорировать.

Возражение что это частный случай исключительно для безнаковых 32-х битных чисел, я хотел бы парировать замечанием, что SIMD инструкции позволяют написать абсолютно аналогичные алгоритмы для знаковых целых чисел и чисел с плавающей запятой одинарной точности. Эффективность работы с числами двойной точностью уже не столь значительна, но продолжает сохраняться.

Будем считать, что метод принимает один единственный параметр, это начала массива, которое в соответствии с соглашением о вызовах VECTORCALL будет расположен в регистре ECX.

Загружаем все 16-ть значений подлежащих сортировки в SIMD регистры. Это первое и последние обращение к памяти для чтения, следующие обращение будет использовано уже для записи отсортированного массива. Таким образом, один раз получив данные, алгоритм вернет уже полностью отсортированный массив максимально сократив количества обращений к памяти.

	movdqa xmm1, [rcx + xmmword * 0]
	movdqa xmm2, [rcx + xmmword * 1]
	movdqa xmm4, [rcx + xmmword * 2]
	movdqa xmm5, [rcx + xmmword * 3]

Буквально 6-ю командами сортируем массив, объединяя числовой ряд в восемь упорядоченных пар.

	movdqa xmm0, xmm2
	pmaxud xmm2, xmm1
	pminud xmm1, xmm0
	movdqa xmm3, xmm5
	pmaxud xmm5, xmm4
	pminud xmm4, xmm3

Следующий шаг это сортировка полученных пар в тетрады и если найти наименьшие/наибольшие не представляется сложным, нужно просто сравнить самое наименьшие/наибольшие число из каждой пары с аналогичным ему числом из другой пары, то нахождение «промежуточных» чисел не так очевидно, но тоже довольно просто. Необходимо найти наименьшие из наибольших и наибольшие из наименьших, после чего уже сравнить и упорядочить их. Для этого потребуеться всего 9 инструкций.

	movdqa xmm0, xmm1
	pminud xmm0, xmm4
	
	movdqa xmm3, xmm2
	pmaxud xmm3, xmm5

	pminud xmm2, xmm5
	pmaxud xmm1, xmm4
	movdqa xmm4, xmm1
	pminud xmm1, xmm2
	pmaxud xmm2, xmm4

Транспонируем полученную матрицу для дальнейшей сортировки. Не берусь утверждать, что представленный код транспонирования наиболее эффективный, возможно его можно сократить на пару тактов, но для демонстрации алгоритма это не критично.

	movdqa xmm4, xmm0
	punpckhdq xmm4, xmm1
	movdqa xmm5, xmm2
	punpckldq xmm5, xmm3
	
	punpckldq  xmm0, xmm1
	movdqa     xmm1, xmm0
	punpcklqdq xmm0, xmm5
	punpckhqdq xmm1, xmm5
	
	punpckhdq  xmm2, xmm3
	movdqa     xmm3, xmm4
	punpckhqdq xmm3, xmm2
	punpcklqdq xmm4, xmm2

Теперь, после транспонирования, в каждом регистре расположены четыре числа упорядоченных по возрастанию. Произведем 4-е сравнения и обмена, в ходе которых произведем объединение 4-х тетрад в 2-е октавы. Стоит заметить, что если в первом сравнения происходит обмен 4-х пар чисел, то на последующих сравнениях количество обменов с каждым разом уменьшается на единицу и в последнем сравнении происходит всего один обмен.

	mov eax, 4
@@:
	movdqa xmm2, xmm1
	pmaxud xmm1, xmm0
	pminud xmm0, xmm2
	pshufd xmm1, xmm1, 10010011b
	
	movdqa xmm5, xmm4
	pmaxud xmm4, xmm3
	pminud xmm3, xmm5
	pshufd xmm4, xmm4, 10010011b
	dec eax
jnz @b

Выполняем последнюю серию сравнений, в ходе которой окончательно упорядочиваем числовую последовательность, сравнивая две октавы.

	mov eax, 8
@@:
	movdqa xmm2, xmm3
	movdqa xmm5, xmm4
	
	pmaxud xmm3, xmm0
	pmaxud xmm4, xmm1
	
	pminud xmm0, xmm2
	pminud xmm1, xmm5
	
	pshufd xmm3, xmm3, 10010011b
	pshufd xmm4, xmm4, 10010011b
	movss  xmm5, xmm3
	movss  xmm3, xmm4
	movss  xmm4, xmm5
	dec eax
jnz @b

Формально, для того чтобы алгоритм можно было считать полным необходимо выполнить запись полученных данных в память.

	movdqa [rcx + xmmword * 0], xmm0
	movdqa [rcx + xmmword * 1], xmm1
	movdqa [rcx + xmmword * 2], xmm3
	movdqa [rcx + xmmword * 3], xmm4

Надеюсь вам было интересно, рад буду услышать интересную, конструктивную критику.

P.S. Эффективность алгоритма значительно возрастает при наличии на целевой машине AVX.