Skip to content

Insertion Sort Implementation in Python

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]
Published inCode Snippets

Comments are closed.