all Python 3Algorithms & data structuresterm

Insertion sort

sorting

O(n²) in the worst case, O(n) for nearly sorted data. It inserts every item into its proper place.

Syntax

def insertion_sort(arr):

It is a teaching algorithm that still earns its keep: Timsort inside list.sort() finishes short runs with insertion sort precisely because on nearly ordered data it approaches O(n). The sort is stable — equal items keep their relative order, which matters when you sort by one key after another. A Python-specific trap: drop the j >= 0 guard from the inner loop and a negative index will not raise IndexError but silently start reading from the end of the list, so the bug shows up only as a wrong result.

Examples

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
    return arr
print(insertion_sort([12,11,13,5,6]))  # → [5,6,11,12,13]
# Трассировка
def ins_trace(arr):
    arr = 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
        print(arr)
    return arr
ins_trace([4,3,1,2])
# Онлайн-алгоритм (добавление элементов)
def ins_insert(sorted_arr, x):
    i = len(sorted_arr)
    sorted_arr.append(x)
    while i > 0 and sorted_arr[i-1] > x:
        sorted_arr[i] = sorted_arr[i-1]
        i -= 1
    sorted_arr[i] = x
    return sorted_arr
result = []
for x in [3,1,4,1,5]:
    ins_insert(result, x)
print(result)  # → [1,1,3,4,5]
# Binary insertion sort
import bisect
def bin_ins_sort(arr):
    result = []
    for x in arr:
        bisect.insort(result, x)
    return result
print(bin_ins_sort([5,3,1,4,2]))  # → [1,2,3,4,5]
# Скорость на почти отсортированных данных
import random
arr = list(range(100))
arr[50] = -1  # один элемент не на месте
print(insertion_sort(arr[:])[:5])  # → [-1, 0, 1, 2, 3]

See also

Open in the full glossarydocs.python.orgReport an inaccuracy