algorithm - 挿入ソート

低速だけど安定で実装しやすい。ほとんど整列済みのデータに対しては高速。
さらに、ソート対象が連結リストであれば、挿入が高速にできるのでバブルソートよりも 大幅に速い。

データを1つずつ、手持ちのデータの中で正しい位置に挿入しながら、
段々とデータ数を増やしていくイメージ。

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        tmp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > tmp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = tmp