Дозатор слияния-обмена

Question

Есть ли у кого-нибудь хорошее руководство / объяснение сортировки слиянием-обменом Бэтчера?

Это не тот же алгоритм, что и битоническая сортировка Бэтчера или нечетно-четная сортировка Бэтчера, хотя многие статьи утверждают, что это так.

Answer 1

Дональд Кнут, Искусство компьютерного программирования , алгоритм 5.2.2M (том III, стр. 111).

Кен Бэтчер (1968), " Сортировка сетей и ихприложение", Учеб.Весенняя объединенная компьютерная конференция AFIPS 32: 307–314.

Answer 2

С http://www.eli.sdsu.edu/courses/spring96/cs662/notes/batcher/batcher.html

Input: N and array A[1:N] of items to sort

set  T = Ceiling(lg(N))

for P = 2T-1, 2T-2, 2T-3, ..., 1 do
R = 0, D = P
for Q = 2T-1, 2T-2, 2T-3, ..., P do
for (K = 1 to N - D ) and ((K-1)   P) = R do in parallel
if A[K] > A[K + D] then
swap(A[K], A[K + D ])
end if
end for
D = Q - P
R = P
end for
end for


(K + 1)   P means logical and of K and P

If number of processors is less than N than the swap becomes a merge

Этот сайт имеет визуализацию этого алгоритма

Answer 3

Простая реализация:)

int FloorLog2(int value)
{
    int result = -1;
    for (int i = 1; i < value; i <<= 1, ++result);
    return result;
}

void BatcherSort(int* array, int length)
{
    int t = FloorLog2(length);
    int p0 = (1 << t);
    int p = p0;

    do
    {
        int q = p0;
        int r = 0;
        int d = p;

        while (r == 0 || q != p)
        {
            if (r != 0)
            {
                d = q - p;
                q >>= 1;
            }

            for (int i = 0; i < length - d; ++i)
            {
                if (((i & p) == r) && array[i] > array[i + d])
                {
                    int swap = array[i];
                    array[i] = array[i + d];
                    array[i + d] = swap;
                }
            }

            r = p;
        }

        p >>= 1;
    }
    while (p > 0);
}