def bubble_sort(lst: list) -> list:
    """Sort a list in ascending order. The original list is mutated and
    returned. The sort is stable.

    Design idea: Swap adjacent out-of-order elements until the list is sorted.

    Complexity: O(n^2) time, O(1) space. Stable and in-place.

    See quicksort, merge sort and heapsort for sorting algorithms with a better
    time complexity.
    """
    # The first iteration will bring the largest element to the end, the second
    # iteration will bring the second largest element to the end - 1, and so on,
    # so we need no more than n iterations to put every element in the proper
    # place.
    for _ in range(len(lst)):
        swapped = False
        for i in range(1, len(lst)):
            # If you changed this comparison to >=, the algorithm would still
            # be correct but the sort would no longer be stable.
            if lst[i-1] > lst[i]:
                lst[i-1], lst[i] = lst[i], lst[i-1]
                swapped = True
        # If no swaps occurred, the list is sorted and we can exit early.
        if not swapped:
            break
    return lst