def insertion_sort(items):
    """Sort given items by taking first unsorted item, inserting it in sorted
    order in front of items, and repeating until all items are in order.
    Running time: O(n^2) because as items grow outter and inner loop both increases, also the function increases in a quadratic way
    Memory usage: O(1) because everything is done in place """

    # similar to selection sort where list is pseudo broken into 'sorted' and 'unsorted' sections
    # an item is selected from 'unsorted' and checks against the 'sorted' section to see where to add

    # this is our selection section of the list
    for i in range(1, len(items)):
        # range is non inclusive so i is never reached only i-1
        # loop through our 'sorted' section
        for j in range(0, i):
            # the moment it finds an item in this part of the list which is greater or equal 'unsorted' selected item, it is removed from the 'unsorted' section and inserted into the 'sorted' section
            if items[j] >= items[i]:
                removed_item = items.pop(i)
                items.insert(j, removed_item)
                # can continue/skip loop cause this part of the list is sorted, which means everything after will be much larger than selected item
                continue
    return items