マージソートのアルゴリズムは与えられた配列データを小さな部分配列に分割し,部分配列ごとにソートを行なう分割統治法の代表的アルゴリズムの一つである.ここでは,マージソートのアルゴリズムの準備として,ソート済みの小さな部分配列を合成してソートされた大きな部分配列を作成するマージという手順を行なうマージ関数を作成してみよう.

問題

与えられた配列データ array[$0$] 〜 array[$n-1$] の部分配列 array[$p$] 〜 array[$q$] と array[$q+1$] 〜 array[$r$] $(p \leq q < r < n)$ をマージするプログラムを作成せよ.

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

実行例

(1)

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

4
1 2 3
1 2 3 4

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

$ ./a.out < merge_data1.txt

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

> 1⊔2⊔3⊔4
> 2

(2)

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

8
1 4 7
2 1 3 4 8 5 6 7

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

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

(3)

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

10
2 5 7
3 2 1 4 11 15 6 9 8 7

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

> 3⊔2⊔1⊔4⊔6⊔9⊔11⊔15⊔8⊔7
> 4

ヒント