Bubble Sort

Bubble sort repeatedly swaps adjacent out-of-order pairs; simple to understand but O(n^2) and rarely used in practice.

Bubbling the largest to the end

Bubble sort walks the array comparing each adjacent pair and swapping them if they are out of order. One full pass guarantees the largest remaining element has moved to its final position at the end, as if it bubbled up. Repeating the pass over the shrinking unsorted prefix eventually sorts everything.

Cost

With n elements the algorithm does about n passes of about n comparisons, so it runs in O(n^2) time in the average and worst cases. An early-exit optimisation stops as soon as a pass makes no swaps, which makes an already-sorted array cost only O(n). It uses O(1) extra memory and is stable, preserving the relative order of equal keys.

• Best case (already sorted, with early exit): O(n)
• Average case: O(n^2)
• Worst case (reverse sorted): O(n^2)
• Extra space: O(1); stable: yes

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                swapped = True
        if not swapped:
            break

How the swaps accumulate

Bubble sort's cost is dominated by adjacent swaps, and the number of adjacent swaps needed to sort an array equals its number of inversions. A reverse-sorted array has the maximum possible inversions, about n^2/2, which is why it is the worst case. Each swap fixes exactly one inversion, so bubble sort can never do better than the inversion count allows.

Why it survives in teaching only

Bubble sort is easy to explain and to prove correct, so it endures as a first example. But it does the maximum possible number of swaps and has poor locality of reference, making it slower than insertion sort even on the small inputs where quadratic sorts are acceptable. Practical libraries never use it, and its main lasting value is as a teaching contrast that motivates the O(n log n) sorts.