ソートプログラムで

質問

１．２つの配列a、bをマージする場合、比較回数が最大となる必要十分条件、最小となる必要十分条件
２．マージソートプログラムと選択ソートプログラムの比較回数について、要素数をｎとしたときに、比較回数をｎで表す
にはどうしたらよいですか？初心者なので全然わかりません。教えてください。

回答No.3

BLUEPIXY

１．
例えば、配列ａの要素数がｎで配列ｂの要素数がｍだとして
ｍ＞ｎでａの要素の最大値がｂの要素の最小値より小さいなら比較回数はｎ回で良くてこの時が最小になるんじゃないかと思います。
逆に最大になる時とは、ａとｂの要素数が同じでデータの大きさの順番が互い違いになるような場合じゃないかと思います。

２．
選択ソートにおける最悪の場合の比較回数については、すでに、以前回答したことがあります。
マージソートの最悪の場合の比較回数については、１．から簡単に求めることができると思います。
合ってるかどうかは、実際のプログラムを書いて動かしてみるといいと思います。