insertion_sort

Insertion Sort Algorithm:
1. Assume the first element of the list is already sorted. Thus, the list is now divided into two sublists: sorted and unsorted.
2. Iterate over the unsorted elements.
3. Save the unsorted elements in a variable so that it doesn't disappear with modified indices after comparison.
4. Iterate over the sorted elements from len(sorted_elements) to 0, in backwards direction so that the unsorted one could be compared and we may find the correct index to insert it in the sorted list.
5. With every iteration in the sorted list, we test if sorted element is greater than the unsorted element, if TRUE, swap the numbers or copy the greater sorted number to the index of smaller unsorted index. Remember, we have already stored current unsorted element being compared to a variable so we can not lose it with this copy.
6. If we are swapping the sorted and unsorted elements, we should decrease the indices by 1 to keep comparing the same unsorted element with other sorted element(we are anyways moving backwards in sorted list/with sorted elements).
7. When the condition in while loop fails, for loop continues which moves forward with another unsorted element and the process continues.

In Brief:
1. Assume the first element of the list is already sorted. Thus, the list is now divided into two sublists: sorted and unsorted.
2. Iterate over the unsorted elements.
3. If the element is less, swap the elements, decrease the indices of both the sorted and unsorted subset so that the correct position of unsorted element is found and it is then inserted.
4. Perform step 2 and 3 recursively or continuously until the indices representing sorted list reach 0.

Insertion sort with swapping elements:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        """val = arr[i]
        j = i
        while j>0 and arr[j-1]>val:
            arr[i], arr[j-1] = arr[j-1], arr[i]
            j -= 1
            i -= 1"""
        for j in range(i-1, -1, -1):
            if arr[j]>arr[i]:
                arr[i], arr[j] = arr[j], arr[i]
                i -= 1
        # both loops are working fine, second one reduces number of lines.
        
 If you have to copy the sorted elements and later place the unsorted element to its correct position:
 
 for i in range(1, n):
        unsorted =  arr[i]
        j = i-1
        while j>=0 and arr[j]>unsorted:
            arr[j+1]=arr[j]
            j-=1
            # print(' '.join(str(i) for i in arr))
        else:
            arr[j+1]=unsorted
            # print(' '.join(str(i) for i in arr))