• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Insertion Sort

← Previous Next →

Insertion sort is one of the simplest and most intuitive sorting algorithms. It works the same way you arrange playing cards in your hand. You pick one card at a time and place it in the correct position among the already sorted cards. This step-by-step approach makes insertion sort easy to understand and useful in many small or partially sorted datasets.

In this tutorial, you’ll learn how insertion sort works, how each value “shifts” into position, how to write the algorithm in Python, when insertion sort performs best and where it is commonly used. This lesson helps strengthen your understanding of elementary sorting techniques.

What Is Insertion Sort?

Insertion sort builds a sorted list by taking one element at a time from the unsorted section and inserting it into the correct position in the sorted section.

The list is conceptually divided into:

  • A growing sorted portion (left side)

  • A shrinking unsorted portion (right side)

Each new element is compared backwards with the sorted part and shifted until it lands in the right spot.

How Insertion Sort Works Step by Step

Let’s take this list:

[7, 3, 9, 1]

Step 1: Start with first element

The first element 7 is considered sorted.

Step 2: Insert 3

Compare 3 with 7 → 3 is smaller
Shift 7 one step to the right
Place 3 at the beginning
List becomes: [3, 7, 9, 1]

Step 3: Insert 9

Compare with 7 → 9 is larger
9 stays in place
List remains: [3, 7, 9, 1]

Step 4: Insert 1

Compare 1 with 9 → shift 9
Compare 1 with 7 → shift 7
Compare 1 with 3 → shift 3
Place 1 at position 0
Final list: [1, 3, 7, 9]

Insertion sort “slides” elements to make room for the new value.

Why Use Insertion Sort?

Insertion sort has several useful advantages:

  • Works very fast on small lists

  • Extremely efficient for nearly sorted data

  • Simple to write and debug

  • Stable sorting (keeps equal elements in order)

  • Requires no extra memory

These qualities make it a common choice in practical scenarios involving small or almost sorted lists.

Insertion Sort Using a Loop

Here’s the standard implementation:

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1

        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1

        data[j + 1] = key

    return data

This code picks each element and shifts others until it fits.

Example Usage

numbers = [8, 2, 5, 1]
print(insertion_sort(numbers))

Output:

[1, 2, 5, 8]

Time Complexity of Insertion Sort

Insertion sort behaves differently depending on how sorted the list already is.

  • Best case: O(n)

  • Average case: O(n²)

  • Worst case: O(n²)

It becomes very slow for large datasets, but shines in situations with nearly sorted data.

When Insertion Sort Works Best

Use insertion sort when:

  • The list is small

  • Data is almost sorted

  • You need a simple, stable method

  • Updates happen frequently and in small chunks

  • Memory must stay minimal

For partially sorted lists, insertion sort can outperform more complex algorithms.

When Insertion Sort Is Not Suitable

Avoid insertion sort when:

  • The dataset is large

  • Sorting needs to be optimized

  • Many comparisons would slow down the system

  • You need very high performance

Algorithms like merge sort or quick sort handle large lists much better.

Real-Life Uses of Insertion Sort

Insertion sort appears in several areas because of its simplicity:

Sorting in small apps

Apps that process tiny datasets often use it directly.

Handling nearly sorted data

Systems where data changes slightly use insertion logic.

Card games and simulations

It matches the logic of arranging cards.

Embedded systems

Tiny memory requirements make it helpful in low-power devices.

Teaching algorithms

It helps beginners understand shifting and insertion.

Step-by-Step Example

List:

[5, 2, 4, 3]

Step 1: Insert 2
→ shifts 5 → [2, 5, 4, 3]

Step 2: Insert 4
→ compare with 5 → shift → [2, 4, 5, 3]

Step 3: Insert 3
→ shift 5 → shift 4 → place 3 → [2, 3, 4, 5]

Final sorted list:

[2, 3, 4, 5]

Practical Examples

Example 1: Sort numbers

print(insertion_sort([4, 1, 9, 2]))

Example 2: Sort words alphabetically

words = ["kiwi", "apple", "grape"]
print(insertion_sort(words))

Example 3: Sort floating values

values = [2.5, 1.1, 4.9, 3.3]
print(insertion_sort(values))

Example 4: Sort names in attendance list

names = ["Asha", "Sara", "Diya"]
print(insertion_sort(names))

Example 5: Sort a hand of cards

cards = [7, 3, 10, 6]
print(insertion_sort(cards))

Example 6: Sort elements manually entered

lst = [int(x) for x in "8 3 6 1".split()]
print(insertion_sort(lst))

Example 7: Sort rating values

ratings = [4.5, 3.2, 4.8, 2.9]
print(insertion_sort(ratings))

Example 8: Sort characters

chars = ['d', 'a', 'c', 'b']
print(insertion_sort(chars))

Example 9: Sort student marks

marks = [78, 45, 92, 67]
print(insertion_sort(marks))

Example 10: Sort dates as strings

dates = ["2024-01-10", "2024-01-01", "2024-01-05"]
print(insertion_sort(dates))

Summary of the Tutorial

Insertion sort works by taking one value at a time and inserting it into the correct position in a growing sorted list. You learned how the algorithm shifts elements, how to implement it in Python, where it performs well and where it becomes slow. Although not meant for large datasets, insertion sort remains a helpful algorithm for understanding sorting and solving small or nearly sorted problems.

Practice Questions

Q1. Write a Python program to sort the list [7, 3, 5, 2] using insertion sort.

Q2. Write a Python program to modify insertion sort to sort a list in descending order.

Q3. Write a Python program to accept a list of numbers from the user and sort them using insertion sort.

Q4. Write a Python program to count and print how many times the array is modified during insertion sort.

Q5. Write a Python program to sort a list of strings alphabetically using insertion sort.

Q6. Write a Python program to print the list after each insertion step during insertion sort.

Q7. Write a Python program to sort only the first half of a list using insertion sort.

Q8. Write a Python program to implement insertion sort without using a separate function (write code directly in the main block).

Q9. Write a Python program to sort a list using reverse logic in insertion sort (from end to start).

Q10. Write a Python program to compare the time taken by insertion sort and selection sort to sort a list of 1,000 random numbers.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top