How to do Insertion Sort in Python

Insertion sort is a simple yet effective algorithm for sorting small datasets. It works similarly to how you might sort playing cards in your hands—picking one card at a time and inserting it into its correct position relative to the other cards. In this blog post, we will go over the implementation of insertion sort in Python, with a clear code example and a diagram to illustrate the sorting process.

---

What is Insertion Sort?

Insertion sort is a comparison-based algorithm that builds a sorted list one element at a time. At each step, it takes one element from the unsorted portion of the list and inserts it into the correct position within the sorted portion.

How Insertion Sort Works:

1. Divide the list into two parts: a sorted and an unsorted section.
2. Take the first element from the unsorted section and compare it to the elements in the sorted section.
3. Insert the element into the correct position by shifting elements in the sorted section to make space if necessary.
4. Repeat the process until all elements are sorted.

Time Complexity:

• Best Case: O(n) — when the list is already sorted.
• Worst Case: O(n²) — when the list is sorted in reverse order.

Insertion Sort Algorithm in Python

Here’s a step-by-step implementation of the insertion sort algorithm in Python:

def insertion_sort(arr):
    # Traverse through 1 to len(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 arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # Insert the key into its correct position
        arr[j + 1] = key

# Example usage:
data = [12, 11, 13, 5, 6]
insertion_sort(data)
print("Sorted array:", data)

Output:

Sorted array: [5, 6, 11, 12, 13]

Diagram Explanation of Insertion Sort:

To better understand how the algorithm works, let’s visualize the sorting process step by step for the input array [12, 11, 13, 5, 6].

Step 1: [12, 11, 13, 5, 6]  (Initial array)
        [12] | [11, 13, 5, 6] (12 is in sorted part)

Step 2: [12] becomes [11, 12] by inserting 11 into the correct position.
        [11, 12] | [13, 5, 6]

Step 3: 13 is already larger than 12, so no changes.
        [11, 12, 13] | [5, 6]

Step 4: 5 is less than 13, 12, and 11, so shift all three and insert 5.
        [5, 11, 12, 13] | [6]

Step 5: 6 is less than 13 and 12, but greater than 5 and 11. So shift 12 and 13, and insert 6.
        [5, 6, 11, 12, 13]  (Final sorted array)

The array is sorted in ascending order by inserting each unsorted element into its proper place in the sorted portion.

Key Points to Remember:

• In-place sorting: Insertion sort does not require additional memory since it operates directly on the input list.
• Stable algorithm: It preserves the relative order of equal elements.
• Efficient for small datasets: It is less efficient for large datasets compared to more advanced algorithms like Quick Sort or Merge Sort but works well for small or nearly sorted data.

Limitations of Insertion Sort

While insertion sort is simple and intuitive, it has some notable limitations:

1. Inefficient for large datasets: With a time complexity of O(n²) in the worst case, insertion sort becomes slow when dealing with large lists.
2. Not suited for complex sorting: Algorithms like quicksort or mergesort are more efficient for handling larger and more complex datasets.
3. High number of comparisons: Insertion sort compares elements multiple times, making it less efficient compared to algorithms that reduce comparisons.

Conclusion

Insertion sort is an intuitive and easy-to-implement sorting algorithm that can be very useful when dealing with small lists or nearly sorted data. In this post, we covered the insertion sort algorithm in Python with a step-by-step breakdown and a diagram to explain the process.

For large datasets, though, you may want to explore more efficient algorithms like merge sort or quick sort, which have better average-case performance.

Congratulations on reading to the end of this tutorial!

For further reading on sorting algorithms in Python, go to the articles:

• How to do Quick Sort in Python (With Code Example and Diagram) 
• How to Do Bubble Sort in Python
• How to Do Selection Sort in Python
• How to do Merge Sort in Python
• How to do Counting Sort in Python
• How to Do Radix Sort in Python
• How to Do Bucket Sort in Python
• How to Do Heap Sort in Python
• How to Do Pigeonhole Sort in Python
• How To Do Comb Sort in Python 
• How to Do Shell Sort in Python

Go to the online courses page on Python to learn more about Python for data science and machine learning.

Have fun and happy researching!