Insertion Sort in Python

The Insertion Sort algorithm is a simple sorting technique that builds the final sorted array 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 has the advantage of being simple to implement and works well for small or nearly sorted arrays.

How Insertion Sort Works

Insertion Sort works similarly to sorting playing cards in your hands. We start with an empty left hand and pick up the cards one at a time. Each new card is inserted into its proper place in the already sorted left hand.

1. Consider the first element of the array to be sorted.
2. Pick the next element.
3. Compare the picked element with all elements in the sorted subarray on its left.
4. Shift all the elements in the sorted subarray that are greater than the picked element to the right.
5. Insert the picked element into its correct position.
6. Repeat until the array is sorted.

Python Implementation of Insertion Sort

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 key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

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

Explanation of the Code

• The function insertion_sort(arr) takes an array as input and sorts it in place.
• key is the element that we want to position correctly.
• The inner while loop compares the key element with its predecessors and shifts them one position ahead if they are greater than the key.
• The key element is then placed in its correct position.
• The process is repeated until the entire array is sorted.

Complexity Analysis

Insertion Sort has a time complexity of O(n^2) in the worst and average cases because of the nested loops. However, in the best case (when the array is already sorted), its time complexity is O(n).

Space complexity is O(1) because it only requires a constant amount of additional space.