Insertion sort in python with explanation

Insertion sort is an algorithm for sorting an array by iterating through the array and inserting each element into its correct position in a sorted sub-array. It works by maintaining a sorted sub-array at the beginning of the array, and inserting each element into its correct position in the sorted sub-array as it iterates through the array.

Here is an example of how you might implement insertion sort in Python:

def insertion_sort(array):

    for i in range(1, len(array)):

        current = array[i]

        j = i - 1

        while j >= 0 and current < array[j]:

            array[j + 1] = array[j]

            j -= 1

        array[j + 1] = current

    return array

array = [4, 3, 2, 1]

sorted_array = insertion_sort(array)

print(sorted_array) # Outputs [1, 2, 3, 4]

In this example, the insertion_sort function takes an array as input and returns the sorted array. It uses a for loop to iterate through the array, and a while loop to find the correct position for the current element in the sorted sub-array. It then inserts the current element into the correct position and continues iterating through the array.