Insertion Sort: Algorithm and Complexity

1. The Core Idea: Sorting One Element at a Time

Insertion sort works much like how you might sort a hand of playing cards. You divide your cards (or your list) into two conceptual parts: a sorted part and an unsorted part. Initially, the sorted part contains only the first element. Then, you pick elements from the unsorted part one by one and "insert" them into their correct position within the sorted part.

This video provides an excellent visual explanation using the card analogy and then applies the concept to an array.

To summarize the process:

1. Assume the first element of the list is a sorted sub-list of size one.
2. Take the next element from the unsorted part (let's call it the key).
3. Compare the key with the elements in the sorted sub-list, moving from right to left.
4. Shift all elements in the sorted sub-list that are greater than the key one position to the right.
5. Insert the key into the "hole" that opens up.
6. Repeat this process until all elements have been moved from the unsorted part to the sorted part.

2. Implementing Insertion Sort in Python

Now let's translate this logic into Python code. The implementation will directly mirror the process you just saw: an outer loop to pick the key element, and an inner loop to handle the comparisons and shifts.

This article provides a very clear, well-commented Python implementation and a line-by-line breakdown.

Here is the code from the article for your reference.

def insertion_sort(array):



    # Loop from the second element (index 1) to the end.
    # The sub-list to the left of `i` is the sorted part.
    for i in range(1, len(array)):



        # The element we want to position correctly.
        key_item = array[i]
        



        # Initialize j to the last element in the sorted part.
        j = i - 1
        



        # Move elements of the sorted part that are greater than key_item
        # one position to their right. This makes space for key_item.
        while j >= 0 and array[j] > key_item:
            array[j + 1] = array[j] # Shift element to the right
            j -= 1 # Move to the next element on the left
            



        # Place key_item in its correct sorted position.
        array[j + 1] = key_item
        
    return array




# --- Let's test it! ---
my_list = [8, 2, 6, 4, 5]
sorted_list = insertion_sort(my_list)
print(f"The sorted list is: {sorted_list}")

another_list = [64, 34, 25, 12, 22, 11, 90]
print(f"Another sorted list: {insertion_sort(another_list)}")

Your Turn: Practice with the Code

1. Create a new Python file and copy the insertion_sort function and the test cases into it.
2. Run the code to see it in action.
3. Trace the algorithm: On a piece of paper, take the list [8, 2, 6, 4] and manually trace the values of i, key_item, j, and the state of the array after each major step of the loops. This is a crucial skill for understanding how algorithms work and for debugging your own code later.

3. Analyzing Time Complexity: O(n²)

You now have a working sorting algorithm. But how efficient is it? Let's analyze its Big O time complexity.

The running time of insertion sort depends on the two nested loops in the code.

• The outer loop runs from the second element to the last. For a list of size n, this loop will run n-1 times. So, it's O(n).
• The inner while loop is where things get interesting. Its number of iterations depends on the data. In the worst-case scenario, it has to shift every single element in the sorted sub-list.

Let's consider the different scenarios.

Worst-Case Complexity: O(n²)

The worst case happens when the input list is sorted in reverse order (e.g., [90, 64, 34, 25, ...]).

• When i=1, the inner loop runs 1 time.
• When i=2, the inner loop runs 2 times.
• ...
• When i=n-1, the inner loop runs n-1 times.

The total number of comparisons is roughly the sum 1 + 2 + 3 + ... + (n-1). As you might know from math, this sum is equal to n * (n-1) / 2. Expanding this gives us (n²/2) - (n/2). In Big O notation, we drop the constants and lower-order terms, which leaves us with O(n²).

This image provides a great visualization of the comparisons adding up in the worst case.

Best-Case Complexity: O(n)

The best case occurs when the list is already sorted.
In this situation, the inner while loop's condition (array[j] > key_item) is immediately false for every element. The inner loop never actually runs. The algorithm simply iterates through the list once with the outer loop. This results in a linear time complexity of O(n). This is a notable strength of insertion sort.

Average-Case Complexity: O(n²)

For a randomly ordered list, on average, each element will have to be shifted past about half of the elements in the sorted sub-list. This still results in a quadratic relationship, so the average-case complexity is also O(n²).

This video segment provides a detailed walkthrough of this complexity analysis, connecting it directly to the algorithm's pseudocode.

For large lists, an O(n²) algorithm is significantly slower than the O(n) of linear search or the O(log n) of binary search. If you tried to sort a list with a million items using insertion sort, it would take a very, very long time!

Conclusion

Great job! You have now implemented and analyzed your first sorting algorithm. While insertion sort's O(n²) complexity makes it unsuitable for sorting massive datasets, its simplicity and efficiency on small or nearly-sorted lists make it a valuable tool in the algorithmic toolkit.

Key Takeaways:

• Insertion sort works by building a sorted sub-list one element at a time.
• It is an in-place algorithm, meaning it sorts the list without requiring extra memory for a new list.
• Its time complexity is O(n²) in the average and worst cases, making it slow for large lists.
• Its best-case time complexity is O(n) when the list is already sorted, which is a key advantage.

Preview of the Next Lesson:
So far, we've seen a linear O(n) search, a logarithmic O(log n) search, and now a quadratic O(n²) sort. Can we do better for sorting? Yes! In the next lesson, we will revisit the "divide and conquer" strategy we first saw with binary search and apply it to sorting. We'll learn about merge sort, a powerful and efficient recursive algorithm with a much better time complexity.