Insertion Sort

In insertion sort, the sorting task is similar to that of sorting a deck of cards.

Algorithm:

1. Start at the beginning
2. Find the next element and bring it to its sorted position

 Time Complexity:

• Best: O(n) - when the list is already sorted
• Worst: O(n2) - when required to reverse the entire list

Space Complexity:

• O(1) - usually no extra space is required 

In-place: yes
Stable: yes

Python Implementation
def insertion_sort(arr):
    n = len(arr)
    for i in range(n):
        j = i
        while j > 0 and arr[j-1] > arr[j]:
            arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1