Python Program for Insertion Sort with Example and Explanation

Insertion sort in Python can be done by looping through the list and inserting each element into its correct position using for and while loops; for example: for i in range(1, len(arr)): key = arr[i]; j = i-1; while j >= 0 and arr[j] > key: arr[j+1] = arr[j]; j -= 1; arr[j+1] = key.

Examples

Input[5, 2, 9, 1]

Output[1, 2, 5, 9]

Input[3, 4, 1, 7, 5]

Output[1, 3, 4, 5, 7]

Input[]

Output[]

How to Think About It

To sort a list using insertion sort, think of sorting cards in your hand. Start from the second element, compare it with elements before it, and move it left until it is in the right place. Repeat this for each element until the whole list is sorted.

Algorithm

1

Start from the second element in the list.

2

Compare the current element with the elements before it.

3

Shift all elements that are greater than the current element one position to the right.

4

Insert the current element into the correct position.

5

Repeat until all elements are sorted.

Code

python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Example usage
numbers = [5, 2, 9, 1]
insertion_sort(numbers)
print(numbers)

Output

[1, 2, 5, 9]

Dry Run

Let's trace the list [5, 2, 9, 1] through the insertion sort code.

1

Start with i=1 (value 2)

Compare 2 with 5; since 5 > 2, shift 5 right and insert 2 at position 0. List becomes [2, 5, 9, 1].

2

i=2 (value 9)

Compare 9 with 5; 5 < 9, so no shift needed. List stays [2, 5, 9, 1].

3

i=3 (value 1)

Compare 1 with 9, 5, 2; all are greater, shift them right. Insert 1 at position 0. List becomes [1, 2, 5, 9].

Iteration	List State
i=1	[2, 5, 9, 1]
i=2	[2, 5, 9, 1]
i=3	[1, 2, 5, 9]

Why This Works

Step 1: Choosing the key element

The element at index i is chosen as the key to insert into the sorted part of the list.

Step 2: Shifting elements

Elements greater than the key are shifted one position to the right to make space for the key.

Step 3: Inserting the key

The key is placed in its correct sorted position, ensuring the left side of the list is sorted.

Alternative Approaches

Using Python's built-in sort

python

arr = [5, 2, 9, 1]
arr.sort()
print(arr)

This is the fastest and simplest way but does not teach the insertion sort algorithm.

Recursive insertion sort

python

def recursive_insertion_sort(arr, n=None):
    if n is None:
        n = len(arr)
    if n <= 1:
        return
    recursive_insertion_sort(arr, n-1)
    last = arr[n-1]
    j = n-2
    while j >= 0 and arr[j] > last:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = last

arr = [5, 2, 9, 1]
recursive_insertion_sort(arr)
print(arr)

Uses recursion instead of loops; less common but good for understanding recursion.

Complexity: O(n^2) time, O(1) space

Time Complexity

Insertion sort uses nested loops; the outer loop runs n times and the inner loop can run up to n times in the worst case, resulting in O(n^2) time.

Space Complexity

It sorts the list in place without extra memory, so space complexity is O(1).

Which Approach is Fastest?

Built-in sort methods are faster for large data, but insertion sort is simple and efficient for small or nearly sorted lists.

Approach	Time	Space	Best For
Insertion Sort	O(n^2)	O(1)	Small or nearly sorted lists
Built-in sort	O(n log n)	O(n)	General purpose, large lists
Recursive insertion sort	O(n^2)	O(n)	Learning recursion, small lists