Insertion Sort in Python

Back to: Python Data Structure and Algorithims

Insertion Sort is a simple and intuitive sorting algorithm. It builds the sorted list one item at a time by comparing the current element with the previous elements and inserting it in its correct position.

Let’s take the example list:

Step 1: How Insertion Sort Works

Start with the second item in the list (index 1).
Compare it with the elements before it.
If it’s smaller, move the larger element one position to the right.
Insert the current element in its correct position.
Repeat for each element in the list until the list is sorted.

Example Walkthrough:

Start with 2 (index 1):
Compare 2 with 6. Since 2 < 6, move 6 to the right and insert 2.
List becomes: [2, 6, 5, 4, 1, 3]
Next, 5 (index 2):
Compare with 6. Since 5 < 6, move 6 to the right. Compare with 2. Since 5 > 2, insert 5.
List becomes: [2, 5, 6, 4, 1, 3]
Next, 4 (index 3):
Compare with 6 → move 6. Compare with 5 → move 5. Compare with 2 → insert 4.
List becomes: [2, 4, 5, 6, 1, 3]
Next, 1 (index 4):
Move 6, 5, 4, 2 one step to the right and insert 1.
List becomes: [1, 2, 4, 5, 6, 3]
Finally, 3 (index 5):
Move 6, 5, 4 one step to the right and insert 3.
List becomes: [1, 2, 3, 4, 5, 6]

Step 2: Coding Insertion Sort in Python

def insertion_sort(my_list):

for i in range(1, len(my_list)):

current_value = my_list[i]

position = i

# Shift elements to the right to make space for current_value

while position > 0 and my_list[position – 1] > current_value:

my_list[position] = my_list[position – 1]

position -= 1

# Insert the current value into its correct position

my_list[position] = current_value

return my_list

Step 3: Running the Function

Output:

Step 4: Notes & Observations

Start from the second element because a single-element list is already “sorted”.
Shift larger elements to the right to insert the current element.
Efficient for small or nearly sorted lists.
Time Complexity: O(n²) in worst case, O(n) in best case.
Space Complexity: O(1) (in-place sorting).