５０時間以内に解けるかな？②

[Merge Sort]

　n個の整数を含む数列Sを以下の疑似コードに従ったマージソートで昇順に整列するプログラムを作成せよ。
また、Mergeにおける比較回数の総数を報告せよ。
プログラムはC, C++, JAVA, C++11, C#, Dいずれかの言語で作成すること。

Merge(A, left, mid, right)
n1 = mid - left;
n2 = right - mid;
create array L[0...n1], R[0...n2]
for i = 0 to n1-1
do L = A[left + i]
for i = 0 to n2-1
do R = A[mid + i]
L[n1] = SENTINEL
R[n2] = SENTINEL
i = 0;
j = 0;
for k = left to right-1
if L <= R[j]
then A[k] = L
i = i + 1
else A[k] = R[j]
j = j + 1

Merge-Sort(A, left, right){
if left+1 < right
then mid = (left + right)/2;
call Merge-Sort(A, left, mid)
call Merge-Sort(A, mid, right)
call Merge(A, left, mid, right)

入力
　１行目にn、２行目にSを表すn個の整数が与えられる。
出力
　１行目に整列済みの数列Sを出力せよ。数列の隣り合う要素は１つの空白で区切ること。２行目に比較回数を出力せよ。

制約
n ≤ 500000
0 ≤ Sの要素 ≤ 109

入力例 1

10
8 5 9 2 6 3 7 1 10 4

出力例 1

1 2 3 4 5 6 7 8 9 10
34

　

[softya（ソフト屋)]

５０時間以内に解けるかな？①が片付くまで凍結させて頂きます。