Which Complexities Do Sorting Algorithms Have?

Bubble sort repeatedly walks the list, swapping neighbours that are out of order, and shrinks the range it scans after each pass. On a list of seven elements it needed twelve swaps to reach sorted order, which is quadratic work for a linear-size input.

def bubble_sort(values):
    data = list(values)
    swaps = 0
    for end in range(len(data) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if data[i] > data[i + 1]:
                data[i], data[i + 1] = data[i + 1], data[i]
                swaps += 1
                swapped = True
        if not swapped:
            break
    return data, swaps

sample = [5, 1, 4, 2, 8, 0, 3]
ordered, swaps = bubble_sort(sample)
print(ordered)
print(swaps)
print(sorted(sample))

All three lines agree on the answer, 0 through 8 in order, but only the second tells you how hard the work was. The early-exit flag is the reason bubble sort is sometimes forgiven: on already sorted data the first pass finds no swap and stops, so it is effectively linear. That is why it is still used as a detection routine for nearly sorted input, never as a general sort.

Python's built-in sort uses Timsort, which detects runs of already ordered data and merges them. On random data it behaves like a merge sort with a guaranteed O of n log n bound and O of n extra space, and on nearly sorted data it is close to linear because the runs it finds are long. The built-in also runs in C, so the constant factor is far smaller than anything you would write in Python.

The trade-off to mention is that the built-in sort is stable, meaning equal elements keep their original relative order, and quicksort is not. If you sort records by one key and need ties to keep another key's order, stability saves you an extra pass. As a general rule, use the library sort unless you have a reason not to, and when you do have a reason, name it: stability, memory limits, or a huge key range.

Merge sort always splits the input in half and always merges two sorted halves, so the number of comparisons it performs depends only on the sizes involved, not on the order of the values. Counting the comparisons inside the merge step shows that.

def merge_sort(values, comparisons=None):
    if comparisons is None:
        comparisons = [0]
    if len(values) <= 1:
        return list(values)
    mid = len(values) // 2
    left = merge_sort(values[:mid], comparisons)
    right = merge_sort(values[mid:], comparisons)
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        comparisons[0] += 1
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

for data in (list(range(8)), list(range(7, -1, -1))):
    counter = [0]
    merge_sort(data, counter)
    print(counter[0])

Both lists produce twelve comparisons. Reversing the input changed which elements were compared but not how many, because every level of the recursion splits eight elements into halves of four, then two, then one, and each merge walks a fixed number of positions.

A naive quicksort that always picks the last element as the pivot behaves completely differently on these two inputs. On sorted data that pivot is the largest remaining element, so each partition peels off a single element and the recursion depth becomes linear, making the total work quadratic. On reverse sorted data the pivot is the smallest, which gives the same degenerate shape. Randomly choosing the pivot, or using the median of three, removes that failure mode and gives O of n log n expected time on any fixed input.

The trade-off to state is that merge sort guarantees its bound and needs linear extra space, while quicksort sorts in place with better cache behaviour and a smaller constant factor, and pays for it with a quadratic worst case. That is why production libraries use Timsort, which takes the best of both: it is a stable merge-based sort that detects existing runs and exploits them.

Bubble sort, insertion sort and selection sort are all O of n squared in the worst case and O of 1 extra space. Selection sort does exactly n squared comparisons regardless of input; insertion sort and bubble sort drop to O of n on already sorted or nearly sorted data, which is why they are used for small or nearly ordered inputs.

Merge sort is O of n log n time in every case, with O of n extra space for the merge buffer. It is stable, so equal elements keep their relative order. Quicksort is O of n log n on average and O of n squared in the worst case, sorts in place with O of log n stack space, and is not stable. Heapsort is O of n log n in every case with O of 1 extra space.

Then there are the non-comparison sorts. Counting sort, radix sort and bucket sort run in O of n plus k time, where k is the size of the key range, and they can beat the n log n barrier because they never compare two keys. The condition is that the keys must be small integers or have a suitable structure; on arbitrary strings, comparisons are still needed.

The trade-off to give is that the choice depends on the input, not on a universal winner. For general-purpose sorting in production, use the library, because Python's Timsort is a stable merge sort that exploits existing runs and beats most hand-written alternatives. Reach for counting or radix sort only when the keys are integers in a known range, and reach for a non-comparison sort only when the key range is small enough that the extra pass over the data pays for itself.