We all know that an **Insertion Sort** is a sorting algorithm. You can find the implementation code of this algorithm is everywhere. But I want to organize this on my site.

## The complexity of this algorithm.

**Worst Complexity:** O( n^2 )**Average Complexity:** O( n^2 )**Best Complexity:** O( n )**Space Complexity:** O( 1 )

def insertion_sort(lst): for i in range(1, len(lst)): item = lst[i] index = i - 1 while index >= 0 and lst[index] > item: lst[index + 1] = lst[index] index = index - 1 lst[index + 1] = item return lst print(insertion_sort([5, 2, 1, 3, 6, 4, 7])) # Output = [1, 2, 3, 4, 5, 6, 7]

Comments are closed.