📌 What is Insertion Sort?

Insertion Sort is a simple, intuitive sorting algorithm that works similarly to how you might sort playing cards in your hands:

You start with the second element, compare it with the one before it, and insert it in the right place.
Then you move to the next element and insert it in the correct position relative to the already sorted part.
You repeat this until the whole list is sorted.

It builds the sorted list one element at a time.

🧠 Key Takeaways from My Learning

Insertion Sort is great for small or nearly sorted datasets.
It has a time complexity of O(n²) in the worst case, but it performs well for small inputs.
The algorithm works in-place, so it doesn’t use extra space.
The main concept is shifting elements to make space for the current item (key).

✅ My Python Code

Here’s the insertion sort implementation I used to practice:

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        key = arr[i]
        j = i - 1

        # Shift elements that are greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Insert the key in the correct position
        arr[j + 1] = key

    return arr

arr = [30, 40, 29, 17, 13, 79]
print(insertion_sort(arr))

🧪 Output

[13, 17, 29, 30, 40, 79]

🚀 Final Thoughts

Insertion Sort gave me a good understanding of how to sort a list incrementally. It’s easy to implement and understand, which makes it a great choice for learning sorting algorithms early in the journey.

What I Learned About Insertion Sort in Python