マージソートアルゴリズムを使用してインプレースソートするにはどうすればよいでしょうか? 質問する

配列 を受け取りxs、2 つのソートされたサブ配列はそれぞれ範囲[i, m)ととして表されます[j, n)。作業領域は から始まりますw。ほとんどの教科書に記載されている標準的なマージ アルゴリズムと比較すると、このアルゴリズムはソートされたサブ配列と作業領域の間で内容を交換します。その結果、以前の作業領域にはマージされたソートされた要素が含まれ、作業領域に格納されていた以前の要素は 2 つのサブ配列に移動されます。

ただし、満たさなければならない制約が 2 つあります。

1. 作業領域は配列の境界内になければなりません。つまり、境界外エラーを起こさずに交換される要素を保持できる大きさでなければなりません。
2. 作業領域は、2 つのソートされた配列のいずれかと重ねることができますが、マージされていない要素が上書きされないようにする必要があります。

このマージ アルゴリズムが定義されていると、配列の半分をソートできるソリューションを想像するのは簡単です。次の質問は、以下に示すように、作業領域に格納されているソートされていない残りの部分をどのように処理するかです。

... unsorted 1/2 array ... | ... sorted 1/2 array ...

直感的なアイデアの 1 つは、作業領域の残りの半分を再帰的にソートすることです。これにより、まだソートされていない要素は 1/4 だけになります。

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

この段階での重要な点は、ソートされた 1/4 要素 B をソートされた 1/2 要素 A と遅かれ早かれマージする必要があることです。

残りの作業領域には 1/4 の要素しか含まれませんが、A と B を結合するのに十分な大きさでしょうか? 残念ながら、十分ではありません。

ただし、上記の 2 番目の制約は、マージされていない要素が上書きされないマージ シーケンスを確保できる場合は、作業領域をいずれかのサブ配列と重なるように配置することでこれを利用できるというヒントを与えてくれます。

実際には、作業領域の後半をソートする代わりに、前半をソートし、次のように 2 つのソートされた配列の間に作業領域を配置することができます。

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

この設定により、作業領域がサブ配列 A と重なり合うように効果的に配置されます。このアイデアは、[Jyrki Katajainen、Tomi Pasanen、Jukka Teuhola。「実用的なインプレース マージソート」。Nordic Journal of Computing、1996] で提案されています。

したがって、残っているのは上記の手順を繰り返すことだけです。これにより、作業領域が 1/2、1/4、1/8 と縮小されます。作業領域が十分に小さくなったら (たとえば、要素が 2 つだけ残った場合)、単純な挿入ソートに切り替えてこのアルゴリズムを終了できます。

以下は、この論文に基づいた ANSI C での実装です。

void imsort(Key* xs, int l, int u);

void swap(Key* xs, int i, int j) {
    Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}

/* 
 * sort xs[l, u), and put result to working area w. 
 * constraint, len(w) == u - l
 */
void wsort(Key* xs, int l, int u, int w) {
    int m;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        imsort(xs, l, m);
        imsort(xs, m, u);
        wmerge(xs, l, m, m, u, w);
    }
    else
        while (l < u)
            swap(xs, l++, w++);
}

void imsort(Key* xs, int l, int u) {
    int m, n, w;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        w = l + u - m;
        wsort(xs, l, m, w); /* the last half contains sorted elements */
        while (w - l > 2) {
            n = w;
            w = l + (n - l + 1) / 2;
            wsort(xs, w, n, l);  /* the first half of the previous working area contains sorted elements */
            wmerge(xs, l, l + n - w, n, u, w);
        }
        for (n = w; n > l; --n) /*switch to insertion sort*/
            for (m = n; m < u && xs[m] < xs[m-1]; ++m)
                swap(xs, m, m - 1);
    }
}