マージソートについて

質問

（８つの数字があり・・・）
１・左端から２つの値をとり、その２つを小さい順に並べ替えます
２・右隣の２つの値をとり、その２つを小さい順に並べ替えます
３・上記１と２で並べ替えた値（合計で４つの値）を小さい順に並べかえます。
４・次に上記３の右隣の４つの数字を上記１，２，３と同じ手順で並べ替えをします。
５・上記３、４で並べ替えた値（合計で８つの値がありますね）を小さい順に並べ替えます。

http://it.exinfo.biz/entry/post_17.html
より、引用。

上記手順３で４つの数字の並び替え、手順５で８つの数字の並び替えをしていますが、何故こんな事をする必要があるのでしょう？というより、わざわざ２つに分けて行く意味なんてあるんでしょうか？？

御解説をお願いします。

回答No.2

chie65536 · ベストアンサー

＞というより、わざわざ２つに分けて行く意味なんてあるんでしょうか？？
大あり。比較の回数が減る。

８個の数値を普通にソートすると
１・１番小さいのを探す（７回の比較が必要）
２・２番目に小さいのを探す（６回の比較が必要）
３・３番目に小さいのを探す（５回の比較が必要）
４・４番目に小さいのを探す（４回の比較が必要）
５・５番目に小さいのを探す（３回の比較が必要）
６・６番目に小さいのを探す（２回の比較が必要）
７・７番目に小さいのを探す（１回の比較が必要）
８・残ったのが８番目（０回の比較が必要）
と言う感じで、合計、２８回の比較が必要。

マージソートだと
１・左端から２つの値をとり、その２つを小さい順に並べ替えます（１回の比較が必要）
２・右隣の２つの値をとり、その２つを小さい順に並べ替えます（１回の比較が必要）
３・上記１と２で並べ替えた値（合計で４つの値）を小さい順に並べかえます（３回の比較が必要）
４・次に上記３の右隣の４つの数字を上記１，２，３と同じ手順で並べ替えをします（１＋１＋３＝５回の比較が必要）
５・上記３、４で並べ替えた値（合計で８つの値がありますね）を小さい順に並べ替えます（７回の比較が必要）
と言う感じで、合計、１７回の比較で終ります。

比較の回数が９回少なくて済むって事は「より早く並び替え出来る」って事。

ソートは「比較回数が減れば減るほど優秀」なので、大いに意味がある。

お礼

なるほど
小さい順に並べ替える、っていうのは、普通のソートみたいに
１番目に小さいのを探す、の繰り返しではなく、
AB　CD
↓
１・AとCを比較、A決定
２・BとCを比較、C決定
３・BとDを比較、B決定、D決定
・・・AとBの比較、CとDの比較は前段階で終わっている

ってことなんですね。

回答No.1

Tacosan

う～ん, ではどうすればいいと思ったんでしょうか?