# Python Program - Insertion Sort

Insertion sort is based on the idea of consuming one element from unsorted array and inserting it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.

### Example:

To understand the insertion sort, lets consider an unsorted array *[23, 1, 10, 5, 2]* and discuss each step taken to sort the array in ascending order. In every pass, one element is taken from the unsorted array and inserted it at the correct position in the sorted array.

** First Pass:** The whole array is unsorted array and

*(23)*is taken to be inserted into the sorted array. As

*(23)*is the first element of sorted array and has no elements to be compared with, it remains at its position.

__Second Pass__:*(1)* is the taken from unsorted array to insert into sorted array. It is compared with all elements of sorted array and found that *(23)* is the only number which is greater than *(1)*. *(1)* is inserted into the sorted array and position of *(23)* is shifted by one place in the array. This resulted into increasing the length of sorted array by one and decreasing the length of unsorted array by one.

__Third Pass__:*(10)* is taken from the unsorted array and compared with all elements of sorted array. *(23)* is the only number in the sorted array which is greater than *(10)*. *(10)* is inserted into the sorted array and position of *(23)* is shifted by one place in the array.

__Fourth Pass__:*(5)* is compared with all elements of sorted array and it is found that *(10)* and *(23)* are the numbers which need to be shifted by one place to insert *(5)* into the sorted array.

** Fifth Pass:** To insert

*(2)*into the sorted array,

*(5)*,

*(10)*and

*(23)*are shifted by one place.

## Implementation of Insertion Sort

# function for insertion sort def insertionsort(MyList): for i in range(len(MyList)): curr = MyList[i] j = i-1 while j >= 0 and curr < MyList[j] : MyList[j + 1] = MyList[j] MyList[j] = curr j = j - 1 # function to print list def PrintList(MyList): for i in MyList: print(i, end=" ") print("\n") # test the code MyList = [1, 10, 23, 50, 4, 9, -4] print("Original List") PrintList(MyList) insertionsort(MyList) print("Sorted List") PrintList(MyList)

The above code will give the following output:

Original List 1 10 23 50 4 9 -4 Sorted List -4 1 4 9 10 23 50

### Time Complexity:

Insertion sort takes maximum time if the array is in the reverse order and minimum time when the array is already sorted. In worst case scenario every element is compared with all other elements. Therefore, for *N* elements there will be *N²* comparison hence the time complexity of insertion sort is *Θ(N²)*.

### Recommended Pages

- Python Program - To Check Prime Number
- Python Program - Bubble Sort
- Python Program - Selection Sort
- Python Program - Maximum Subarray Sum
- Python Program - Reverse digits of a given Integer
- Python Program - Merge Sort
- Python Program - Shell Sort
- Stack in Python
- Queue in Python
- Python Program - Find LCM of Two Numbers
- Python Program - To Check Whether a Number is Palindrome or Not
- Python Program - To Check Whether a String is Palindrome or Not
- Python Program - Heap Sort
- Python Program - Quick Sort
- Python - Swap Two Numbers without using Temporary Variable
- Python Program - To Check Armstrong Number
- Python Program - Counting Sort
- Python Program - Radix Sort
- Python Program - Find Largest Number among Three Numbers
- Python Program - Print Floyd's Triangle