# Python program for insertion sort

In this post, you will learn about **insertion sort** and how to write an insertion sort program using the **Python** programming language.

The **Insertion Sort** is a very simple technique, it inserts each item in the proper place in the final list. Insertion sort is less effective as compared to the other sorting techniques. In this, the array elements are divided into two parts.

## Insertion sort example

These are the insertion sorting techniques.

Search for the element that is less than the first element. **A[1] < A[0]**, so interchange them.

Next, search for the next element that is less than the first element. **A[2] < A[0]**, so interchange them.

Now there is no element in the right which is less than the first element. Similarly, we repeat the same process for **A[1]**, **A[2]** and **A[3]**.

While sorting of **A[3]**, we found **A[3] > A[4]**, so we interchange them.

Finally, we get the sorted array element.

## Complexity of Insertion sort

Suppose **n** is the number of elements in an array.

`Best Time Complexity - `**O(n)**
Worst Time Complexity - **O(n**^{2})
Average Time Complexity - **O(n**^{2})

## Insertion sort Algorithm

```
insertionSort(array)
mark first element as sorted
for each unsorted element X
'extract' the element X
for i <- lastSortedIndex down to 0
if current element i > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort
```

## Insertion sort program in Python

In the given Python program, we create a function **insertion_sort()** that takes an array as an argument. Inside the function, we create a for loop with a loop variable **i** that counts from 1 to the length of the array. Next, we set a variable **key** equal to the element at index **i** and set **j** equal to **i – 1**. We create a while loop that runs as long as **j** is non-negative and key is smaller than the element at index **j**. Within this loop, we set the element at index **j + 1** equal to the element at index **j** and decrement **j**. When the while loop finishes, we set the element at index **j + 1** equal to **key**.

```
# Insertion sort in Python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are greater than key,
# to one position ahead of their current position
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
# Place key at after the element just smaller than it.
arr[j+1] = key
# main
# Initializing array
arr = [42, 55, 23, 64, 12, 66, 32, 14, 16, 63]
insertion_sort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
print (arr[i])
```

**Output of the above code:**

```
The sorted array is:
12
14
16
23
32
42
55
63
64
66
```

### Related Articles

**Convert Python list to numpy array**

Convert string to list Python

Python program to list even and odd numbers of a list

Python loop through list

Sort list in descending order Python

Convert array to list Python

Python take screenshot of specific window

Web scraping Python BeautifulSoup

Check if two strings are anagrams Python

Python program to add two numbers

Print new line python

Python for loop index

Convert List to Dataframe Python

numpy random choice

Dictionary inside list python

Check if list is empty Python

Python raise keyword

Python program to get the largest number from a list

Python program to map two lists into a dictionary

Convert string to list Python

Python program to list even and odd numbers of a list

Python loop through list

Sort list in descending order Python

Convert array to list Python

Python take screenshot of specific window

Web scraping Python BeautifulSoup

Check if two strings are anagrams Python

Python program to add two numbers

Print new line python

Python for loop index

Convert List to Dataframe Python

numpy random choice

Dictionary inside list python

Check if list is empty Python

Python raise keyword

Python program to get the largest number from a list

Python program to map two lists into a dictionary