
整列済みデータの併合とマージソート
用語の意味
併合は、二つの整列済みの列を一つの整列済みの列にまとめる処理です。マージソートでは列を分割し、それぞれ整列してから併合します。
解き方と例
昇順なら左右の未処理部分の先頭を比較し、小さい方だけを出力してその側を一つ進めます。片方が空になれば残りを続けて出力できます。各要素を一度ずつ出力するため、併合にかかる処理量は要素数の合計に比例します。
確認問題【オリジナル】
[2, 6, 9]と[1, 4, 8]を併合するとき、先頭3件と、その直後に比較する2値は何ですか。
答えと解説
出力は1、2、4です。左は6、右は8が未処理部分の先頭になるため、次は6と8を比較します。