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) It can iterate through all elements on each loop
    Memory usage: O(1) Sorting is done in place, only ints declared
    """
    # Loop through the whole array
    for i in range(1, len(items)):
        # While the element is less than the element before it, swap them
        # Stop swapping if there are no elements before it
        j = i
        while items[j] < items[j - 1] and j > 0:
            items[j], items[j - 1] = items[j - 1], items[j]
            j -= 1
    return items