# Explain Insertion Sorting with example in Data Structures and Algorithm?

235 views
Explain Insertion Sorting with example in Data Structures and Algorithm?
posted Feb 10, 2015

### Insertation Sorting:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

### Code:

``````def insertionSort(alist):
for index in range(1,len(alist)):

currentvalue = alist[index]
position = index

while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)
``````

### Algorithm

``````for i = 2 to n,
for (k = i; k > 1 and a[k] < a[k-1]; k--)
swap a[k,k-1]
invariant: a[1..i] is sorted
end
``````

### Properties

Time Complexity: O(n^2)
Space Complexity: O(1) extra space
Best Case: O(n) time when nearly sorted