Параллельность достигается за счет того что на каждом шаге обращение к каждому элементу происходит не более 1 раза: массив условно разбивается на 2 не пересекающиеся группы элементов, сравнение и обмен происходит между элементами этих групп, при этом каждому элементу из первой группы соответствует не более одного элемента из второй и наоборот (связь [0..1]:[0..1]). Соответственно в рамках одного шага операция сравнение и обмен может производится одновременно для всех пар элементов.
Поскольку операция сравнения и обмена выполняется для двух элементов из разных групп, то во время прохода по массиву для элементов первой группы берется соответствующий компаньон среди элементов второй группы, а элементы из второй группы пропускаются. Элемент относится к первой группе если выполняется условие (i & mask) == offset, при этом маска всегда равна степени двойки, а смещение либо равно нулю, либо маске.
Значение маски с каждым шагом уменьшается 2 (единичный бит смещается вправо), начальное значение определяется как наибольшее целое число, такое что 2^t < N, где N - размер массива:
mask(0) = initValue = 2^t
2^t < N <= 2^(t+1)
2^t < N <= 2*2^t
initValue < N <= 2*initValue
Индекс компаньона определяется смещением (дистанцией). Дистанция зависит от текущего значения маски и количества выполненных проходов для текущего значения маски. При первом проходе дистанция равна маске. Для последующих проходов дистанция определяется как разница между одним из предыдущих значений маски и текущим. Соответственно с каждым проходом дистанция сокращается и так до тех пор пока дистанция больше либо равна маске. Далее маска уменьшается в 2 раза и цикл повторяется. Размер дистанции для текущего значения маски сначала равен mask, а далее изменяется от 2^t до mask, при этом на первом шаге в начале массива стоят элементы первой группы, на последующих - второй. После того как значение маски достигло 1, выполняется последняя серия проходов по массиву. Теперь массив отсортирован.
mask = [2^t..1]
mask(x) = mask(x-1)/2
dist(0) = mask
dist(>0) = [2^t..mask]
prevMask = [2^t..mask]
dist(y) = prevMask(y-1) - mask(x)
- p - mask
- q - prevMask
- d - dist
