Insertion sort Algorithm in Python

Insertion sort is a simple sorting algorithm that builds the final sorted array (or 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.

An analogy to understand the Insertion Sort algorithm is to imagine sorting a deck of cards. To sort a deck of cards, you would go through each card one by one, and insert it into the correct place in your hand, making sure that the hand you hold is always sorted. This is the same process that Insertion Sort follows.

Here’s the code in Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key_item = arr[i]
        j = i - 1
        while j >= 0 and key_item < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item
    return arr

print(insertion_sort([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]))

The output of the code will be:

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

1. The function insertion_sort takes an array arr as an argument.
2. The first for loop (for i in range(1, len(arr))) iterates through the array starting from the second element (index 1) and ending at the last element (index len(arr) - 1).
3. In each iteration of the for loop, a variable key is set to the current element arr[i].
4. Another variable j is set to i-1 to keep track of the index of the previous element.
5. The while loop (while j >= 0 and key < arr[j]) compares the key with the previous element. If key is less than the previous element, the previous element is shifted one position to the right to make room for the key.
6. The loop continues until j is no longer greater than or equal to 0, or until key is not less than the previous element.
7. When the while loop ends, the key is inserted into its correct position by assigning it to arr[j + 1].
8. The for loop continues until all elements have been processed.
9. Finally, the sorted array is printed with the print statement.

When should it be used?

• When the list is small, Insertion sort is an efficient way to sort the list.
• When the list is mostly sorted, Insertion sort performs well because the number of shifting operations is minimal.

Limitations:

• It has a time complexity of O(n^2) in the worst-case scenario, making it less efficient for large data sets.
• It is not suitable for larger data sets or data sets that are not partially sorted.