def bubble_sort(items):
    """Sort given items by swapping adjacent items that are out of order, and
    repeating until all items are in sorted order.
    Running time: O(n**2) because it passes through n/2 (on average) elements
        n-1 times, which simplifies to n elements n times, n**2
    Memory usage: O(1), as only a boolean and two integers are declared
    """

    # Take up to n-1 passes
    for j in range(len(items) - 1):
        # Bool for checking if items were swapped
        swapped = False

        # Last item after each pass is always sorted and can be ignored
        for i in range(len(items) - 1 - j):

            # Swap items if the current is greater than the next
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True

        # If there were no swaps, list is already sorted
        if not swapped:
            return items
    return items