Python Insertion Sort

Python Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted list one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it provides several advantages:

• Simple implementation.
• Efficient for small data sets.
• Efficient for data sets that are already substantially sorted.
• It is an "in-place" algorithm (requires a constant amount of extra memory space).

How Insertion Sort Works

Imagine you are sorting a hand of playing cards. You pick up one card at a time and insert it into its correct position in the cards you are already holding.

1. Start with the second element of the list (assume the first element is a sorted sublist of one).
2. This is the key element you want to insert into the sorted sublist.
3. Compare the key with the elements in the sorted sublist, moving from right to left.
4. Shift all elements in the sorted sublist that are greater than the key one position to the right.
5. Insert the key into the gap you've created.
6. Repeat this process for all elements in the list.

Implementing Insertion Sort in Python

Here is a function that implements the insertion sort algorithm.

def insertion_sort(data):
    # Traverse through 1 to len(data)
    for i in range(1, len(data)):
        key = data[i]
        # Move elements of data[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < data[j]:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key

--- Usage ---
my_list = [12, 11, 13, 5, 6]
insertion_sort(my_list)
print("Sorted list is:", my_list)

Time Complexity

• Best Case: O(n) - If the list is already sorted, the inner while loop is never entered, and it only takes one pass.
• Worst Case: O(n²) - If the list is sorted in reverse order.
• Average Case: O(n²)