挿入ソートとは
挿入ソート（Insertion Sort）とは、データ群を並び替えるためのアルゴリズムの一つです。配列を「すでに整列し終わった部分」と「まだ整列していない部分」に分け、未整列の部分からデータを1つずつ取り出し、整列済みのデータ群の中の「正しい位置」を探して差し込み（挿入し）ていくことで、全体をソートします。すでにある程度整列されているデータに対して非常に速く動作します。
具体例
手札のトランプカードを整理する際、新しくめくったカード（未整列）を手元のすでに数字順に並んでいるカード（整列済み）の中を見て、適切な位置に差し込む（挿入する）日常的な動作と同じです。
# 挿入ソートのプログラム例
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 正しい位置に挿入もう少し詳しく
挿入ソート（Insertion Sort）は、配列を「整列済みの部分」と「未整列の部分」の2つに分け、未整列の部分から要素を1つずつ取り出して、整列済みの部分の適切な位置に割り込ませて（挿入して）いくソートアルゴリズムです。初期状態では、先頭の1要素（インデックス0）だけを「整列済み」とみなし、残りを「未整列」とします。次に、インデックス1の要素を取り出し、整列済みのカード（インデックス0）と比較して、左側に置くべきか右側に置くべきかを判定して挿入します。これを繰り返して、整列済みの壁を右へスライドさせていきます。挿入する際には、挿入先より右側にある整列済みデータをすべて1つずつ右にシフトして空きスペースを作る必要があります。平均および最悪の時間計算量は O(N^2) ですが、このアルゴリズムの特筆すべき長所は、「データが最初からある程度整列されている場合」に劇的に高速に動作する点にあります。完全に整列済みのデータを入力した場合、データのシフトが発生しないため、比較回数は N-1 回で済み、計算量は O(N) となります。また、安定ソートであり、メモリを追記で消費しない（インプレース）ため、シンプルながら実用性の高いアルゴリズムです。
試験でのポイント
試験では、挿入ソートの「すでに整列に近い状態であるデータに対して非常に高速に動作する（最良の計算量は O(N) になる）」という最大の特徴が非常によく出題されます。アルゴリズムのトレース問題では、取り出した値を左側の整列済みデータと順番に比較し、適切な位置を見つけて割り込ませる過程での「データの右シフト（代入処理）」がどのように行われているかをソースコードから読み取る能力が求められます。
関連する用語
インプレース（追加のメモリをほとんど使わず、元の配列内で処理を完結させる方式）、シフト（配列の要素を隣のインデックスへ移動させる処理）、シェルソート（挿入ソートを改良した高速な整列アルゴリズム）。