sorting - 挿入ソートを使用してほぼソートされた配列をソートする

Question

1. ほぼソートされた配列での挿入ソートに関しては、線形時間がかかります。しかし、それは、配列がソートされている場合にループから抜け出すためのif条件が実装にある後でのみですよね??

2. 小さなデータセットでの挿入ソートの場合、なぜ挿入ソートが好ましいのですか？クイックソートとマージソートにマップされた比較/操作の量が少ないためですか？

Answer 1

はい、比較ループから非常に早く抜け出すため、ほぼ並べ替えられた配列では線形時間がかかります。要素を適切な場所に挿入したら、ソートされた配列の残りの部分を調べる必要はありません。

すでにソートされている配列の知識を利用しているからだと思いますが、クイックソートでは各要素を適切な場所に移動してから、残りの要素をソートします。