特殊目的の整列法 Batcher奇遇マージソート

シャッフル（完全シャッフルと完全逆シャッフル）と比較交換走査だけを使った整列法をBatcher奇遇マージソートという。

完全シャッフル

ファイルの第一要素、次に後半部分の第一要素、次に前半部分の第二要素、後半部分の第二要素というように並べ、前半部分にあった要素は偶数部分に移動し後半部分にあった要素は奇数の場所に移動する。

完全逆シャッフル

偶数の場所にある要素を前半部分、奇数の場所にある要素を後半部分に移動する。

プログラム11.1　完全シャッフルと完全逆シャッフル

shuffle(Item a[], int l, int r) {
    int i, j, m = (l+r)/2;
    for (i = l, j = 0; i <= r; i += 2, j++) {
        aux[i] = a[l+j];
        aux[i+1] = a[m+1+j];
    }
    for (i = l; i <= r; i++) a[i] = aux[i];
}

unshuffle(Item a[], int l, int r) {
    int i, j, m = (l+r)/2;
    for (i = l, j = 0; i <= r; i += 2, j++) {
        aux[l+j] = a[i];
        aux[m+1+j] = a[i+1];
    }
    for (i = l; i <= r; i++) a[i] = aux[i];
}

プログラム11.2　Batcher奇遇併合（再帰版）
逆シャッフルにより独立に併合する問題で半分の大きさのものを二つ作る。それぞれの部分ファイルを前半後半で併合しその解をシャッフルした後に隣同士比較交換していく。説明しにくいがプログラムを見れば分かると思う。

#include <stdio.h>
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) {Item t = A; A = B; B = t;}
#define compexch(A, B) if (less(B, A)) exch(A, B)

typedef char Item;
char aux[16];

shuffle(Item a[], int l, int r) {
    int i, j, m = (l+r)/2;
    for (i = l, j = 0; i <= r; i += 2, j++) {
        aux[i] = a[l+j];
        aux[i+1] = a[m+1+j];
    }
    for (i = l; i <= r; i++) a[i] = aux[i];
}

unshuffle(Item a[], int l, int r) {
    int i, j, m = (l+r)/2;
    for (i = l, j = 0; i <= r; i += 2, j++) {
        aux[l+j] = a[i];
        aux[m+1+j] = a[i+1];
    }
    for (i = l; i <= r; i++) a[i] = aux[i];
}

mergeTD(Item a[], int l, int r) {
    int i, m = (l+r)/2;
    if (r == l+1)
        compexch(a[l], a[r]);
    if (r < l+2) return;
    unshuffle(a, l, r);
    mergeTD(a, l, m);
    mergeTD(a, m+1, r);
    shuffle(a, l, r);
    for (i = l+1; i < r; i+= 2)
        compexch(a[i], a[i+1]);
}

int main(void) {
    char ar[] = {'A', 'G', 'I', 'N', 'O', 'R', 'S', 'T',
                 'A', 'E', 'E', 'L', 'M', 'P', 'X', 'Y'};
    mergeTD(ar, 0, 15);
    int i;
    for (i = 0; i < 16; i++)
        printf("%c\n", ar[i]);
    
    return 0;
}

実際にデバッグしてみると納得する。結構簡単にできるので感動する。