並べ替えるという動作を考えたとき、
という２つの動作が必要です。この並べる基準というのが、実は大切で、これが曖昧だと、どんな方法をつかっても並べられません。数値の大小のように、明確な場合はいいのですし、「優劣付け難し」の場合ならそれをまとめておけばいいのですが、「三すくみ」になったら、いつまでも終わらなくなってしまいます。今回は、最終目的が、指定された場所から近い順に交差点を決める、ということなので、距離を基準にします。
次に並べる方法です。これもいろいろあります。トランプみたいに１枚ずつしか無いことが保障されていれば、場所を決めて置いていくだけで（７ならべのように）、順に並べることができます。ところが、並べる対象の持つ値の範囲が０〜数万に渡ったり、小数だったり、だぶることもあったりすると、そうはいきません。そこで、普通はデータ群から２つ取ってきて比較して、入れ替える、といった方法をとります。
なんでもいいからならべる、と言うなら話は簡単です。ところが、莫大な量のデータをソートする場合、その並べ替えの速度、というものが問題になってきます。データが少ないうちはほとんど差がなくとも、データが多くなるにつれて、方法によって大きな差がでてきます。そのため、並べ替えの方法というのが重要になってくるわけです。今回はだれでも分かる(と願ってますが)ごく簡単な方法から、速度重視の方法までやります。なにも、コンピュータの中だけではなく、現実世界で手で並べ替えるのも速くなるかも知れませんよ。 (人間には直感という強力な武器はあるのですが）
並べ替えるという動作は、「順番を決めるために大小を判断する」という動作と、それを実際に並べる・入れ替える操作からなります。
順番を決めるための大小判断は、サーチでもちょっと出てきたように、絶対的基準でも、相対的基準でもいいので、とにかく、大小が分かるようにすればいいわけです。
ところが、この比較も、実際のデータの移動もそれなりに手間がかかるわけです。ここで示す例のように、数字一つくらいなら、どちらもかわりませんが、アルファベット順に並べるためにstrcmp()をつかったり、もっと複雑な評価をしたりすれば時間がかかります。データの移動は、多少の工夫で処理量を減らすことはできますが、少ないに越したことはありません。 そのため、「並べ替え方」が重要になります。
とはいえ、最初から難しいのをやると、頭がこんがらかると思うので、全部をむりに理解することはありません。最低ひとつ、自分で納得するようにしてください。
これから４つ(＋改良版)の方法を示します。プログラムにしてみて、ちゃんと並べ替え出来たら、教えてください。
並べ替える対象は、面倒なので、ただの数字にします。要素数はN(例では8)にしました。また、だぶりが無いことにします。もちろん、すべての方法は数字がだぶっても問題なく動きますが、見た目わかりにくくなるので、こうしました。また、小さい順にならべます。大きい順に並べるには、評価の部分の 符合を反対にするだけです。
バブルソートと呼ばれる、並べ替え法は、データの配列をひたすら隣り同士で比較し、望む順番でなければ入れ替える、という形になってます。大事なのは隣同士で比較・交換というところです。どこから比較しても似たような ものな気がしますが、前から順番に [0]と[1]、[1]と[2] と比較していきます。そのため、先頭に大きな数字があると、[0] -> [1], [1] -> [2]とどんどん動いていくので、泡が水中を登る様に例えてバブルというらしいです。（逆に、下りるほうはなかなか下りてきません）。
この方法のソートは終了条件の決め方で若干速度がかわります。 ここでは、最初は[0]:[1] から [N-2]:[N-1] までいきますが、最後の方の比較が不要になったら、上限である upを下げてくるようにしています。
/* バブルソート */
void sort0(void) {
int i, j;
int lo = 0, up = N - 1;
while (up > lo) {
j = lo;
for (i = lo; i < up; i++) {
/* 順序が正しくなければ */
if (compare_data(i, i + 1) > 0) {
/* 交換 */
exchange_data(i, i + 1);
j = i;
}
}
up = j;
}
}数値の移動の様子
| [6 7] 0 5 1 3 4 2 | 最初二つを比較して、並べ替え
| 6 [0 7] 5 1 3 4 2 | 次の二つを比較して、並べ替え
| 6 0 [5 7] 1 3 4 2 |
| 6 0 5 [1 7] 3 4 2 |
| 6 0 5 1 [3 7] 4 2 |
| 6 0 5 1 3 [4 7] 2 |
| 6 0 5 1 3 4 [2 7]| ７はここまで来ました。
| [0 6] 5 1 3 4 2 7 |
：このプログラムで、compare_data(a, b) は配列要素[a]と [b]を比較し、[a]が大きいなら正を、[b]が大きいなら負を返すように してあります。また、exchange_data(a, b)は要素[a]と [b]を交換します。
このように、大きな数字から右に寄せてくる感じで並べていきます。
終了条件がよく理解できない場合
/* バブルソート（判断なし） */
void sort0_(void) {
int i, j;
for (j = N - 1; j > 0; j--) {
for (i = 0; i < j; i++) {
/* 順序が正しくなければ */
if (compare_data(i, i + 1) > 0)
/* 交換 */
exchange_data(i, i + 1);
}
}
}内側に、[0]:[1]〜[j-1]:[j] のループがあって、j は N-1 から 1 まで下りてきます。バブルソートの特性により、内側のループ一回で、 必ず [0]〜[j]の最大値が[j]に動いてくるので、これでも並べ替えができるのです。ただし、無条件に全部調べるので、無駄に遅くなることがあります。
この方法は、一番小さなもの(小さな順の場合)を探して、それを先頭に持ってくる、というアイデアです。１回目は全部 [0]〜[N-1]から最小のものを探して先頭にもってきます。２回目は先頭を除いた配列[1]〜[N-1]から、この範囲で最小のものを探して ここでの先頭、すなわち[1]に置きます。つまり、小さな順に探しては 置いていく、という形です。
見つけた要素は、先頭にもってくるときには「交換」にします。そうすることで、もともと先頭にあったけど最小でなかったものは、後ろにいって、 次回以降の対象になります。最初から先頭にあった場合、同じ場所で入れ替えるだけ無駄なのですが、例外をふやすと分かりにくくなりそうなので、以下のサンプルでは省きました。
/* 選択ソート */
void sort1(void) {
int i, j, max;
for (i = 0; i < N - 1; i++) {
/* いまのところ 最大の要素がある位置(変化します) */
max = i;
/* すでに決まった分 i個を除いた最大要素検索 */
for (j = i; j < N; j++)
if (compare_data(max, j) > 0)
max = j;
/* それを先頭におく */
exchange_data(i, max);
}
}並べ替えの様子
| (6 7 [0] 5 1 3 4 2)| () は検討対象の範囲
| 0 (7 6 5 [1] 3 4 2)| [] は見つけた最小値で()の先頭に移動
| 0 1 (6 5 7 3 4 [2)|
| 0 1 2 (5 7 [3] 4 6)|
| 0 1 2 3 (7 5 [4] 6)|
| 0 1 2 3 4 (5] 7 6)|
| 0 1 2 3 4 5 (7 [6)|
| 0 1 2 3 4 5 6 7 |この最小要素を探すところは、サーチの最も近いものを探すと同じアルゴリズムです。maxは暫定最小値の場所を指していて、比較して挑戦者が勝てばそこに変ります。
ここから 多少ややこしくなりますが、速くなります。「クイック」なんて 名前もついてますし。
上二つの方法が、与えられた配列をそのまま処理するのに対して、このクイックソートと次に説明するマージソートは、小分けにしていく特徴があります。また、関数が自分自身を呼び出す、「再帰呼出」というテクニックを使います。
クイックソートを言葉で説明すると、以下のようになります。
なんとなくは分かると思います。さて、第２段階で左半分と右半分をソートするために何を使うかというと、もちろん、同じ方法を使うわけです。この段階で「与えられた配列」は左半分、右半分となります。どんどん小分けにしていくと、最後には要素一つの配列になってしまいますが、その部分はソートが完了してたことになります。
プログラムで書くと、こんな感じです。
static void sort2r(int st, int en) {
/* 真ん中あたりを基準にする */
int l = st,
r = en,
ref = (st + en) / 2;
while (1) {
while (compare_data(ref, l)>0)
l++;
while (compare_data(ref, r)<0)
r--;
if (l >= r)
break;
exchange_data(l, r);
/* 基準要素も移動 */
if (ref == l)
ref = r;
else if (ref == r)
ref = l;
l++;
r--;
}
/* ここで st - l - 1 は [st] より小, r + 1 - en は [st]より大 */
if (l - 1 > st)
sort2r(st, l - 1); /* 分けて１個でなければ それを再度処理 */
if (r + 1 < en)
sort2r(r + 1, en); /* 分けて１個でなければ それを再度処理 */
}
/* 上の関数を呼ぶだけ */
void sort2(void) {
sort2r(0, N - 1);
}sort2r(st, en)が上の方法をプログラムにしたものです。 並び替える範囲を [st]〜[en]に限定してます。
前半の while (1){} が、与えられた配列の[ref]要素を基準に左右にわけます。 ここで、ref はどこでもいいのですが、とりあえず、真ん中あたりにしています。
分割が終わると、[st]〜[l-1]が左半分、[r+1]〜[en]が右半分になり、それぞれ要素数が1で無い場合に、その範囲を並べるように sort2r を呼んでいます。この再帰呼出の場合には、呼ばれた関数の l や r の変数は 呼ぶ側の関数の l や r とは全く関係ないため、こういうことをしても、 全く問題はおきません(言語によっては問題になりますが)。
さらに、この関数をそのまま外から呼ぶわけにもいかないので、 sort2()という、起動専用の関数をつくって、sort2rに 全配列を渡すようにしています。
さて、実行すると、こんな感じです。
| (6 7 0 5 1 3 4 2)| [0]-[7]を５を境に分割
| (2 4 0 3 1) (5 7 6)| [0](2)-[4](1) と [5]-[7]
| (2 4 0 3 1) 5 7 6 | [0]-[4]を０を境に分割
| (0) (4 2 3 1) 5 7 6 | [0]-[0], [1]-[4]
| 0 (4 2 3 1) 5 7 6 | [1]-[4]を２を境に分割
| 0 (1) 2 (3 4) 5 7 6 | [1]-[1], [3]-[4]
| 0 1 2 (3 4) 5 7 6 | [3]-[4]
| 0 1 2 (3) (4) 5 7 6 | ここまでで [0]-[4]は完了
| 0 1 2 3 4 (5 7 6)| [5]-[7],6
| 0 1 2 3 4 (5 6) (7)|
| 0 1 2 3 4 (5 6) 7 | [5]-[6],5
| 0 1 2 3 4 (5) (6) 7 |時と場合によって、境界が含まれることも含まれないこともあったりしてますが、左右に分けるアルゴリズムの関係です。
これまでのソートは基本的に「入れ替え」でデータの並べ替えをしていました。 この場合、整列すべき配列の他に、仮の入れ物が1個必要になります。 a と b を入れ替えをするためには
temp=a; a=b; b=temp;のようなプログラムをつくります。このために、仮の入れ物 temp が必要になります（数値だけの場合は、算術演算だけで済む荒業がありますが）。
さて、クイックソートが左右に分けた上で、それぞれをさらにソートする、というアルゴリズムだったのに対して、このマージソートは、とりあえず二つに分けて、それぞれを並べてから、それを組み合わせる＝マージする、というアルゴリズムです。さらに、マージしたものを格納するため、元配列と同じ大きさの領域を必要とする、という性質があります。場所は食うのですが、クイックソートよりも高速で、どんなデータでも要素数が同じなら、同じ比較回数・移動回数で処理が終了します。
また、言葉で説明してみましょう。
たぶん、この方法は一度くらい現実でやったことがあるのではないでしょうか？全部をこの方法でやらないにしても、何人かで作業するとき、適当にわけて割り振りって、それぞれ並べ替えてから、最後にまとめますよね。そんな感じの方法です。
プログラムを示します。
/* マージソート1(難儀) */
/* 添字 st から en までを 並び替えます, 自分自身を呼び出します */
static void sort3r(int st, int en)
int c = (st + en) / 2; /* だいたい真ん中 */
int w = N; /* 結果の一時格納先 */
int i, j;
/* データを二つの山を二つに分けて、それぞれソート(１個ならしない) */
if (c - st > 0)
sort3r(st, c); /* [st - c] の並び替え */
if (en - (c + 1) >0)
sort3r(c + 1, en); /* [(c+1) - en] の並び替え */
i = st;
j = c + 1;
/* 両方の山とも残ってる */
while ((i <= c) && (j <= en)) {
/* 前の山の上が大きければ後ろの山から一つとる */
/* そうでなければ前の山から一つとる */
if (compare_data(i, j) > 0) {
move_data(w, j); w++; j++;
}
else {
move_data(w, i); w++; i++;
}
}
/* この時点ではどちらかの山のみ,残ってるので 処理する */
/* 前の山が残ってる */
while (i <= c) {
move_data(w, i); w++; i++; /* 前の山から一つとる */
}
/* 後ろの山が残ってる */
while (j <= en) {
move_data(w, j); w++; j++; /* 後ろの山から一つとる */
}
/* 作業場から戻す */
for (i = st, w=N; i <= en; i++, w++)
move_data(i, w);
}
/* 上の関数を呼ぶだけ */
void sort3(void) {
sort3r(0, N - 1);
}クイックソートよりは、分かりやすいと思います。とりあえず、真ん中 あたりの c でわけて、 [st]-[c] と [c+1]-[en] をソートします。 そのあと、作業エリアに積みながらマージしていきます。ちなみに、作業エリアとしては、ソート対象配列が [0]-[N-1] にあるのに対して、 [N]-[2N-1] を使うようにしています。最後の for 文があやしげな 構文になっていますが、最初に i = st と w = N が一緒に実行されて、 一回毎に i++, w++ が実行される、という便利な書き方です。「,」で ならべるだけです。ただし、真ん中のループ終了条件のところは、一つしか書けませんのでお気をつけを。例によって、起動専用の関数が別にあります。
さて、実行結果です。
[0-7]を並び替えるために、[0-3]を並び替えるために、[0-1]を並び替えます。
← ソート領域 → ← 作業領域 → [] は空
| 6 7 0 5 1 3 4 2 | [] [] [] [] [] [] [] []
作業エリアに並べます 。
| [] [] 0 5 1 3 4 2 | 6 7 [] [] [] [] [] []
もどします。
| 6 7 0 5 1 3 4 2 | [] [] [] [] [] [] [] []
同じく [2-3]。
| 6 7 0 5 1 3 4 2 | [] [] [] [] [] [] [] []
| 6 7 [] [] 1 3 4 2 | 0 5 [] [] [] [] [] []
| 6 7 0 5 1 3 4 2 | [] [] [] [] [] [] [] []
並び替えられた [0-1]と[2-3]をマージして、[0-3]をつくります。
| 6 7 0 5 1 3 4 2 | [] [] [] [] [] [] [] []
6 vs 0 で 0、 6 vs 5 で 5、 あとは 6,7(ただ移動)
| [] [] [] [] 1 3 4 2 | 0 5 6 7 [] [] [] []
| 0 5 6 7 1 3 4 2 | [] [] [] [] [] [] [] []
[4-5] 済
| 0 5 6 7 1 3 4 2 | [] [] [] [] [] [] [] []
[6-7] 済
| 0 5 6 7 1 3 2 4 | [] [] [] [] [] [] [] []
[4-7] 済
| 0 5 6 7 1 2 3 4 | [] [] [] [] [] [] [] []
並び替えられた [0-3]と[4-7]をマージして、[0-7]をつくります。
| 0 5 6 7 1 2 3 4 | [] [] [] [] [] [] [] []
| [] [] [] [] [] [] [] [] | 0 1 2 3 4 5 6 7
| 0 1 2 3 4 5 6 7 | [] [] [] [] [] [] [] []このように右側の領域に、まぜながら並べては戻し、をします。１回の入れ替え作業が、３回の移動を伴うのに対して、この場合は 移動２回です。ただし、全データが必ず移動するので、移動量は多くなります (後述)。ちなみに、要素数が２のｎ乗でない場合は、当然半端にわかれて いきます。そして、最後の方で ３＝２＋１になって、２の方をソートしてそれと１のほうをマージする、という形になります。気になる人は 後ろのサンプルを試してみてください。
ここに今までのソートプログラムの雛型があります。 バブルソートのみ実装してありますので、他のソートも実装して実行してみてください。 これらが理解できるようになれば、ソートに関してはほぼ完璧です。
map2.datのデータに対して、入力された座標から近い交差点順にデータを並べ替えて出力させます。ソートのアルゴリズムもバブルに限定しません。上の様々なソートが理解できれば好きなものを使ってください。ちなみに、単純選択法は説明するのが難しい方法で実装してあるので、まねしないことをお勧めします。（近い順に出力はしますが、ソートはしていませんし）
下に課題のプログラムの雛型を示しますが、やろうとしていることは、
たとえばこういうデータがあった場合、
0,0.00,0.00,30,駅前青葉,Ekimae-Aoba,3,41,38,40
1,0.86,7.55,30,七北田入口,Nanakita-Iriguchi,2,2,3
2,0.62,6.72,30,泉中央駅,Izumi-Chuoh-Station,3,1,4,3
3,1.36,6.52,30,免許センター,Menkyo-Center,3,1,2,5
4,0.28,5.85,30,八乙女駅,Yaotome-Station,4,2,7,10,5読み込んだばかりのcross[i]の中にはそれぞれ、
cross[0]←交差点番号0の駅前青葉
cross[1]←交差点番号1の七北田入口
cross[2]←交差点番号2の泉中央駅
cross[3]←交差点番号3の免許センター
cross[4]←交差点番号4の八乙女駅が入っています。それを、たとえばある地点から近い順に八乙女駅・泉中央駅・駅前青葉・免許センター・七北田入口だったとしたとき、
cross[0]←交差点番号4の八乙女駅
cross[1]←交差点番号2の泉中央駅
cross[2]←交差点番号0の駅前青葉
cross[3]←交差点番号3の免許センター
cross[4]←交差点番号1の七北田入口というデータにしたい訳です。
以下のプログラムをひな形にしてください。こちらからもダウンロードできます。
/** ex8-2.c 交差点のソート
* キーボード入力した座標から近い順にデータを並び変えて画面に出力するプログラム）
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#define CROSSING_SIZE 100 /* 交差点数=100 */
#define MAX_NAME_SIZE 50 /* 最大文字数50文字(半角) */
typedef struct {
double x, y; /* 位置 x, y */
} Position; /* 位置を表す構造体 */
typedef struct {
int id; /* 交差点番号 */
Position pos; /* 位置を表す構造体 */
double wait; /* 平均待ち時間 */
char jname[MAX_NAME_SIZE]; /* 交差点名 */
char ename[MAX_NAME_SIZE]; /* 交差点名 */
int points; /* 交差道路数 */
int next[5]; /* 隣接する交差点番号 */
} Crossing;
Crossing cross[CROSSING_SIZE];
int map_read(char *filename) {
/* サーチで作ったものを参考にして下さい */
}
void print_cross(int i) {
/* サーチで作ったものを参考にして下さい */
}
/* ここら辺から入力してください */
/* num個表示 = 表示数制限可能 */
void print_cross_list(int num) {
int i;
for (i = 0; i < num; i++)
print_cross(i);
}
/* バブルソートのプログラムを入力して下さい：元気がある人は他のも試してみましょう */
void bubble_sort(int num, double x0, double y0) {
int i, j, lo, up;
double d1, d2; /* 距離を計算します */
Crossing temp; /* 入れ替えのために使ってください */
lo = 0;
up = num - 1;
while (up > lo) {
j = lo;
for (i = lo; i < up; i++) {
d1 = hypot(cross[i].pos.x - x0, cross[i].pos.y - y0); /* 交差点 i から (x0,y0) までの距離 */
d2 = hypot(?????????????? - x0, ?????????????? - y0); /* 交差点 i+1 から (x0,y0) までの距離 */
if (d1>d2) {
/* 逆順なので i と i+1 を入れ替えましょう */
/* temp を使ってください */
temp = cross[i]; /* 入れ替え第１手順 */
cross[i] = cross[i+1]; /* 入れ替え第２手順 */
cross[i+1] = ??????????; /* 入れ替え第３手順 */
j = i;
}
}
up = j;
}
}
int main(void) {
int crossing_number; /* 交差点数 */
double x, y;
/* ファイルの読み込み */
crossing_number = map_read("map2.dat");
printf("loaded %d crossings\n", crossing_number);
/* fprintf(stderr,... にすると、| more , | less などの影響を */
/* 受けなくなります */
fprintf(stderr, "基準座標を入力してください (%%lf %%lf 形式):\n");
scanf("%lf %lf", &x, &y);
bubble_sort(crossing_number, x, y);
print_cross_list(crossing_number);
return 0;
}以下に実行例を示します。元気がある人は、別のソートも試して みましょう。
$ ./ex8-2
loaded 90 crossings
基準座標を入力してください (%lf %lf 形式)->
0 0
交差点番号: 0, 座標( 0.00, 0.00), 名前: 駅前青葉 ( Ekimae-Aoba ),
待ち時間: 30.0, points:3, adjacent crossing( 41 38 40 )
交差点番号:40, 座標(-0.02,-0.12), 名前: 駅前南町 ( Ekimae-Minamimachi ),
待ち時間: 30.0, points:2, adjacent crossing( 0 39 )
交差点番号:38, 座標(-0.20,-0.03), 名前: 愛宕上杉青葉 ( Atago-Kamisugi-Aoba ),
待ち時間: 30.0, points:4, adjacent crossing( 0 36 37 39 )
交差点番号:39, 座標(-0.14,-0.15), 名前: 愛宕上杉南町 ( Atago-Kamisugi-Minamimachi ),
待ち時間: 30.0, points:4, adjacent crossing( 40 38 42 47 )
交差点番号:41, 座標(-0.06, 0.22), 名前: 駅前広瀬 ( Ekimae-Hirose ),
待ち時間: 30.0, points:2, adjacent crossing( 36 0 )
交差点番号:36, 座標(-0.30, 0.22), 名前: 愛宕上杉広瀬 ( Atago-Kamisugi-Hirose ),
待ち時間: 30.0, points:4, adjacent crossing( 41 21 35 38 )
交差点番号:42, 座標(-0.44,-0.28), 名前: 東二番丁南町 ( Higashi-2Bancho-Minamimachi ),
待ち時間: 30.0, points:4, adjacent crossing( 39 37 43 46 )マージ、という点でも、作業領域を食う、という点でも、同じですが、処理の順序がかわっていて、再帰呼出も使いません。 このマージソートは以下の手順になります。
/**
* マージソート(2) (関数1個)
* 先頭から2個ずつとってそれぞれソート, 4個ずつ... 2^n
*/
void sort4(void) {
int i, j;
int src = 0; /* 現在のもと位置 */
int dest = N; /* 現在の格納先 */
int slice = 1; /* 処理する単位 */
int p1, p2; /* 比較点１, ２ */
int L1, L2; /* 比較長１, ２ */
/* 処理する単位が全長を越えたらおしまい */
while (slice < N) {
/* 先頭から i番目の (slice*2)個のデータ塊を処理 */
for (i = 0; i < N; i += slice * 2) {
p1 = i; p2 = p1 + slice; /* マージする対象２こ */
L1 = slice; L2 = slice; /* それぞれの長さ */
if (p1 + L1 > N) L1 = N-p1; /* 存在するデータ長の確認*/
if (p2 + L2 > N) L2 = N-p2; /* 存在するデータ長の確認*/
p1 = p1 + src; p2 = p2 + src; /* 現在データのある場所 */
j = dest + i; /* 格納先 */
/* 系列１、２両方残ってる */
while ((L1 > 0) && (L2 > 0)) {
/* 系列１の先頭が小さければ */
if (compare_data(p1, p2) < 0) {
move_data(j, p1); /* 系列１(p1) から 出力 */
j++; p1++; L1--;
}
else {
move_data(j, p2); /* 系列２(p2) から 出力 */
j++; p2++; L2--;
}
}
/* この時点ではどちらかの山のみ,残ってるので 処理する */
while (L1 > 0) {
move_data(j, p1); /* 系列１(p1) から 出力 */
j++; p1++; L1--;
}
while (L2 > 0) {
move_data(j, p2); /* 系列２(p2) から 出力 */
j++; p2++; L2--;
}
}
slice *= 2; /* 扱うデータの長さを倍 */
i = src; src=dest; dest=i; /* 格納場所を入れ替え */
}
/* 必要なら、もとのところに戻しましょう */
if (src > dest) {
for (i = 0; i < N; i++)
move_data(dest + i, src + i);
}
}マージの直前に、例外処理のための部分があって多少うっとうしいですが、上の第1段階〜第n段階まで、同じプログラムで書くとこんな感じになります。 この方法には、じつは前の方法にはない、特徴があります。見て分かる範囲では、最後になるまで、作業域から結果領域に移動する、という作業が無いため、移動回数がへります。それとは別に、これが流れ作業向きにできている、という特徴があります。
たとえば、６４個のデータの組があるときに、６人の人がいたとしましょう。１人目の人は２個ずつとって、並べて、次の人に渡します。２人目の人は、２個単位で１人目に渡されたデータを、マージして４個組にして３人目に。６人目は３２個単位で並べ終わったデータをもらって、まとめて６４個のソート済データをつくります。なんか、最後の人が比較の回数は多いようですが、こうすると流れ作業で処理できます。特にこの６４個の組が沢山あるとき、かたっぱしからいけます。
さらに面白いことに、６人目のひとは、５人目の人から３２個の組を二つとももらわなきゃ作業が開始できないようにも見えるのですが、実は、１組目の３２個が来て、２組目の１個が来た段階で作業を開始できるのです（データの出力速度が同じとした場合）。なぜなら、例え、一組目全要素より、二組目全要素が大きい場合にも、５人目からもらうデータをただ、出力していけばいいのです。そうでない場合には、２組目が貯まっていくことでしょう。つまり、
時間の経過→
入力 ：６７０５１３４２
１人目出力： ６７０５１３２４ （７も来ると 比較出力できる）
２人目出力： ０５６７１２３４ （０まで来ると比較開始できる）
３人目出力： ０１２３４５６７となるわけです。データを順に流し込むだけで、出力からは順番にデータがでてくるわけです。で、某企業はこれをハードウェアにしてます。一人一人の仕事は単純なので、電子回路でも処理できるわけです。
なお、これを現実世界でやってみて、うまくいくかは保障しません。たぶん、受け渡しの段階で、ときどきへまって変なことになるでしょう。やっぱり、山分けして、最後にだれかがまとめた方がいいと思います。