Insertion sort

  1. Create two subarrays. The subarray at the beginning is not sorted but the subarray at the end is not.
  2. Start at array[1]
def insertion_sort(arr):

    # start at 1 because the first element is sorted.
    for i in range(1, len(arr)):
        # cv = current value
        # cp = current position
        cv = arr[i]
        cp = i

        while cp > 0 and arr[cp - 1] > cv:
            arr[cp] = arr[cp - 1]
            cp = cp - 1

            arr[cp] = cv


# Array is sorted in acending order, we want it decending.
array = [4, 8, 12, 16, 20, 24]
insertion_sort(array)
print("sorted array: " + str(array))

Khan Academy example