挿入ソート

挿入ソートは、整列済みの部分に、未整列の要素を1つずつ取り出して、正しい位置に挿入していく整列の方法です。

■ 試験で押さえるポイント

• 計算量はO(n²)ですが、ほぼ整列済みのデータではとても速くなります。

• 同じ値の順序が保たれる（安定な）方法です。

■ 過去問での着眼点

ほぼ整列済みのデータに強い点を押さえます。

例: トランプの手札を、1枚ずつ正しい位置に差し込んで並べるのと同じです。