- [[ソートアルゴリズム]]の一つ - キーから左が常にソートされるようにしつつ、キーを常に右にずらしていく - キーより左が常にソートされているとすれば、 # 擬似コード ``` for j = 2 to A.length key = A[j] i = j - 1 // ここで、常にkeyより左側がソート済みになるようにしてる while i > 0 && A[i] > key A[i+1] = A[i] // flip i = i - 1 A[i+1] = key ``` # 計算量 - 最悪計算量: $O(N^2)$