挿入ソートの仕組み・コード・計算量をわかりやすく解説

考え方を平易に説明

最初の要素を、長さ1のソート済みリストとして扱います。2番目の要素を取り出して、最初の要素の前か後ろに挿入します。3番目の要素を取り出して、最初の2つの中の正しい位置に挿入します。すべての要素が挿入されるまで続けます。

挿入するには、新しい要素を脇に取っておき（これを key と呼びます）、ソート済み部分を左に向かってたどります。key より大きい要素はすべて1つ右に動かします。key より大きくない要素か、リストの先頭に着いたら、空いたスロットに key を置きます。

具体例をステップごとに見る

[12, 11, 13, 5, 6] をソートします。バーより前の部分はソート済みです（ただし、まだ最終的な位置とは限りません）。

ステップ2に注目してください。すでに正しい位置にある要素は、比較1回で済みます。挿入ソートがほぼソート済みの入力で速いのはこのためです。

Pythonでの実装

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

交換ではなくずらす方式なら、動かした各要素の書き込みは1回で済み、交換ベースの版の約半分の作業量です。以下のように、二分探索で挿入位置を見つけることもできます。そうすると比較回数は全体で O(n log n) に減りますが、ずらす操作は依然として O(n²) なので、全体の時間は O(n²) のままです。

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

時間計算量と空間計算量

より正確には、実行時間は O(n + I) です。ここで I は転倒数（順序が逆になっているペアの数）です。すべての要素が最終位置から高々 k 個しか離れていなければ、I は最大でも n · k なので、挿入ソートは O(n · k) になり、k が小さいと非常に高速です。

挿入ソートと他のソートの比較

挿入ソートが安定なのは、要素が厳密に大きい要素だけを越えて左へ動くからです。また、オンライン処理ができるという性質もあります。データが届くたびにソートでき、どの時点でもソート済みの先頭部分を保てます。短いリストでは、オーバーヘッドの小ささにより O(n log n) のアルゴリズムより速いため、Timsort（Pythonや、Javaのオブジェクトのソートで使われています）は短いランを二分挿入ソートでソートし、多くのクイックソートの実装も、ある小さなサイズ以下では挿入ソートに切り替えます。

派生と、よくある間違い

• 二分挿入ソート：位置を二分探索で見つけてから、ずらします。比較回数が減るため、比較が高コストな場合に有効です。
• シェルソート：一定の間隔だけ離れた要素に挿入ソートを適用し、その間隔を 1 まで縮めていきます。遠く離れた要素を素早く動かせるので、大きな配列では単純な挿入ソートよりずっと高速です。
• 連結リストでの挿入ソート：要素をずらす必要はありませんが、位置を見つけるには依然として線形走査が必要です。

挿入ソートを使う場面

小さな配列（数十要素）、ほぼソート済みのデータ（たとえば、ソートした後に数個だけ追加されたリスト）、そして単純で安定なインプレースのソートが必要な場合に使います。大きなランダムデータには、O(n log n) のソートを使ってください。Pythonでは sorted() か list.sort() で、これらはすでに内部で小さなランに挿入ソートを適用しています。

面接では、手順の追跡、最良ケースと最悪ケース、安定である理由、小さな入力やほぼソート済みの入力で O(n log n) のアルゴリズムに勝る理由などがよく問われます。