マージソートが外部整列に向いている理由。

質問

現在ソート方法について学んでいます。
色々と調べながら勉強を進めているのですが、

マージソートは外部整列に向いている。

とよく書かれているものの、
「なぜ」外部整列に向いているのかが分かりません。

パソコンの知識が乏しい者ですので、出来るだけ初心者でも分かりやすい説明をして頂けると助かります。
宜しくお願い致します。

回答No.1

sakusaker7 · ベストアンサー

>「なぜ」外部整列に向いているのかが分かりません。
テープデバイスのように順次アクセスしかできないようなものに格納されたデータでもソートできるから。

とはいえよくあるアルゴリズムの解説本では、順次アクセスしかできない場合のプログラム片はあまり載ってないような気がします。

"Merge sort is so inherently sequential that it's practical to run it using slow tape drives as
input and output devices. It requires very little memory, and the memory required does not change with
the number of data elements. If you have four tape drives, it works as follows:

1. Divide the data to be sorted in half and put half on each of two tapes
2. Merge individual pairs of records from the two tapes; write two-record chunks alternately to each of the two output tapes
3. Merge the two-record chunks from the two output tapes into four-record chunks; write these alternately to the original two input tapes
4. Merge the four-record chunks into eight-record chunks; write these alternately to the original two output tapes
5. Repeat until you have one chunk containing all the data, sorted --- that is, for log n passes, where n is the number of records.

For the same reason it is also useful for sorting data on disk that is too large to fit
entirely into primary memory. On tape drives that can run both backwards and forwards,
merge passes can be run in both directions, avoiding rewind time.
"
http://en.wikipedia.org/wiki/Merge_sort

#日本語版の記述はひどいな…

回答No.2

notnot

外部ソートって、そもそもマージソートくらいしか手法が無いのでは？
内部ソートだといろいろ手法があり、データの性質を仮定できないときは、その中では平均的に早いクイックソートが使われることが多いです。

ソート済みのたくさんのデータ列をまとめてソートしたいときは、内部であれ外部であれ、マージソートが適しています。