マージソートのアルゴリズムは部分配列のソートとマージの再帰的な手続で記述することができる.問題 2-4 で作成したマージ関数を用いてマージソートのアルゴリズムを実装してみよう.

問題

与えられた配列データをマージソート(merge sort)により昇順に並べ替えるプログラムを作成せよ.また,「ふたつの数の比較」の回数を数えよ.

プログラムは以下の仕様を満たすこと(以下の仕様を満たしたプログラムに5点を加点する).

実行例

(1)

入力されるデータファイル (mergesort_data1.txt) の例

2
1 2

リダイレクション ‘<’ を用いて mergesort_data1.txt の内容を標準入力から読み込む.

$ ./a.out < mergesort_data1.txt

mergesort_data1.txt に対する実行結果の例(> は標準出力を示し, は半角スペースを示す.)

> 1⊔2
> 1

(2)

入力されるデータファイル (mergesort_data2.txt) の例

4
4 3 2 1

mergesort_data2.txt に対する実行結果の例(> は標準出力を示し, は半角スペースを示す.)

> 1⊔2⊔3⊔4
> 4

(3)

入力されるデータファイル (mergesort_data3.txt) の例

8
2 4 3 1 8 7 6 5

mergesort_data3.txt に対する実行結果の例(> は標準出力を示し, は半角スペースを示す.)

> 1⊔2⊔3⊔4⊔5⊔6⊔7⊔8
> 13

ヒント