マージソートで、昇順に整列済みの2つの列 1, 4, 7, 9 と 2, 3, 8, 10 を、先頭どうしを比べて小さい方を出力することを繰り返して1つの列にまとめる(マージする)。片方の列が空になったら、残りは比べずにそのまま出力する。比較の回数は何回か。

正解：B. 7回

1と2、4と2、4と3、4と8、7と8、9と8、9と10を比べ、ここで最初の列が空になるので残りの10は比べずに出力します。比較は7回で、長さ m と n の列をマージするときの最大の回数 m + n − 1 = 7 に当たります。マージは整列済みの列を先頭から1回ずつ見るだけなので O(m + n) で済み、これを log₂ n 段繰り返すのでマージソート全体は O(n log n) になります。

• A. 片方の列の長さだけ比べれば済むわけではありません。値が交互に出るので比較が多くなります。
• B. 正しい。最後の10だけが比べずに出力され、比較は7回です。
• C. 最後の1つは比べる相手がいないので、8回にはなりません。