これに最も適したソート方法は？

Question

質問;

あなたは日付で銀行取引の配列をソートする必要があります。それらのほとんどは （日付で）順番になっていますが、少数のものが故障しています。

配列がほぼソートされているという事実を利用するために、挿入ソート、選択 ソートとマージソートの間でどのソートアルゴリズムを使用しますか？

私の答え（その正しい場合はわからない）

N> = 5、私はその平均以来、マージソートとなるだろうと仮定。時間の複雑さはO（n * log n）であり、これは挿入ソートO（n^2）よりも効率的である。ただし、複数のトランザクションが同じ日付になるため、挿入ソートは安定したソート方法となります。

どちらの方が良いでしょうか？マージまたは挿入の並べ替え？私は正しい方向にいますか？

Answer 1

安定性のためにではなく、適応性があり（here参照）、入力がほぼソートされているために優れているため、挿入の並べ替えを選択する必要があります。

この「適応的」特性の意味は、既に存在する要素がO（1）時間で処理され、そのソートされた位置に非常に近い要素もO（1）とみなすことができるということです距離）。