Insertion Sort is a simple, comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by taking each element from the unsorted portion and inserting it into its correct position in the sorted portion by shifting larger elements to the right. This algorithm is efficient for small or nearly sorted datasets but has a time complexity of O(n²) in the worst case. It is stable, in-place, and widely used in practical scenarios where minimal data movement is required.

For example, consider the array [10, 4, 5, 8, 0]. In each iteration we get a part of the complete array. We start from the array of 1 element, this is [10]. The array is sorted, because it is only one element. Next step we get the array [10, 4]. We get the last element of the array, that is number 4, and we try to sorted by checking with the rest of the array elements. In this case we compare 4 with 10, 4 is smaller than 10, so we "insert" 4 in the front of 10 and we get the array [4, 10]. Next step we have the array[4,10,5]. We get the last element of the array, that is number 5 and we compare it with the rest of the elements. So, 4 is smaller than 5, 5 is smaller than 10. So we "insert" 5 between 4 and 10 and we get the array [4, 5, 10]. We continue the same algorithm until the end of the array.

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

    # Example usage
    arr = [10, 4, 5, 8, 0]
    insertion_sort(arr)
    print("Sorted array:", arr)
                                        

Algorithm Complexity

Insertion sort time complexity, as bubble sort, is O(n²) and it is a very similar algorithm and not very efficient.