Insert Sort

Insertion sort is a simple sorting algorithm that works by iterating through the list of items to be sorted, taking each item and inserting it into its proper place in the sorted list. It does this by repeatedly swapping the item with its predecessor until it is in the correct position.

Here’s the basic outline of the algorithm:

1) Iterate through the list of items, starting at the second item (index 1). For each item:
2) Save the item in a temporary variable.
3) Set a variable j to the item’s index.
4) While j is greater than 0 and the item at index j-1 is greater than the temporary variable:
5) Set the item at index j to the item at index j-1.
6) Decrement j by 1.
7) Set the item at index j to the temporary variable.

function insertion_sort(array):
    for i in 1 to length of array - 1:
        temp = array[i]
        j = i
        while j > 0 and array[j-1] > temp:
            array[j] = array[j-1]
            j -= 1
        array[j] = temp
    return array