Insertion Sort in Python

Insertion sort is a simple sorting algorithm that builds the final sorted  list one item at a time. It is much less efficient.

Best-case performance: O(n) comparisons,
Average performance:О(n2) comparisons
Worst-case space complexity:О(n) total

Example:
x=[98,67,85,67,85,47]
>>> def insertion_sort(x):
for i in range(1,len(x)):
j=i
while j>0 and x[j]<x[j-1]:
x[j],x[j-1]=x[j-1],x[j]
j=j-1
return k

>>> insertion_sort(x)

[6, 7, 12, 32, 43, 45]