Sorting I: Bubble, Insertion, Selection

What “sorting” means

To sort a list is to rearrange its items into order, usually smallest-to-largest (ascending). A list in Python is an ordered collection of values written with square brackets, like [5, 2, 4, 1]. Sorting that list produces [1, 2, 4, 5].

Sorting matters because ordered data is easier to work with. You can find the smallest or largest item instantly (it is at an end), you can search it quickly, and duplicates sit next to each other. Many harder algorithms assume their input is already sorted.

Python has a built-in sorted() function and a .sort() method, and in real code you should use them. We study these three hand-written sorts because they teach how ordering actually happens, one comparison and one swap at a time.

A few terms we will use throughout:

• Element / item: one value in the list.
• Index: the position of an element, counted from 0. In [5, 2, 4], the 5 is at index 0, the 2 at index 1.
• Swap: exchange the values at two positions. In Python: a[i], a[j] = a[j], a[i].
• Comparison: checking whether one value is greater than another, e.g. a[i] > a[j].
• Pass: one full sweep through the list.

All three algorithms below are comparison sorts: they only ever compare two elements and possibly swap them. They all run in O(n²) time on a list of n elements, which we derive at the end. They sort in place, meaning they rearrange the original list without building a second big list, so they use O(1) extra space.

Bubble sort

The idea: walk through the list comparing each pair of neighbors. If a pair is out of order (left bigger than right), swap them. After one full pass, the largest element has “bubbled” to the far right. Repeat for the rest.

def bubble_sort(a):
    n = len(a)
    for i in range(n):                 # n passes
        for j in range(n - 1 - i):     # compare neighbors, shrink each pass
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]   # swap
    return a

print(bubble_sort([5, 1, 4, 2]))   # -> [1, 2, 4, 5]

range(n) produces the numbers 0, 1, ... n-1, so the outer loop runs n times. The inner loop shrinks by i each pass because the last i elements are already the largest and settled.

Short trace on [5, 1, 4, 2], showing the array after each swap in pass 1 (comparing neighbors left to right):

After pass 1 the largest value, 5, is parked at the right end. Later passes settle 4, then 2, giving [1, 2, 4, 5].

Optimization worth knowing: if a whole pass makes zero swaps, the list is already sorted and you can stop early. That makes bubble sort O(n) on an already-sorted list.

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:      # nothing moved this pass -> done
            break
    return a

Selection sort

The idea: find the smallest element in the list and put it at the front. Then find the smallest of what remains and put it in the second slot. Repeat. Each pass “selects” the next-smallest element.

def selection_sort(a):
    n = len(a)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):      # scan the unsorted part
            if a[j] < a[min_index]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]   # one swap per pass
    return a

print(selection_sort([5, 1, 4, 2]))   # -> [1, 2, 4, 5]

Note the difference from bubble sort: selection sort does at most one swap per pass (it does all the looking, then one exchange), while bubble sort may swap many times per pass.

Short trace on [5, 1, 4, 2]. The | marks the boundary between the sorted front and the unsorted rest:

Insertion sort

The idea models how many people sort playing cards in hand. You keep a sorted section on the left. You take the next element and slide it leftward, past every element larger than it, until it lands in the right spot. Then that section is sorted and one element longer.

def insertion_sort(a):
    for i in range(1, len(a)):     # a[0] alone is trivially sorted
        key = a[i]                 # the element we are inserting
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]        # shift the larger element right
            j -= 1
        a[j + 1] = key             # drop key into the gap
    return a

print(insertion_sort([5, 1, 4, 2]))   # -> [1, 2, 4, 5]

Two details for the beginner. key is a copy of the value we are placing, saved before we start overwriting positions. The while loop shifts each too-large element one slot to the right, opening a gap; when the loop stops, a[j + 1] is that gap, and we drop key there.

Watch the sorted region grow one element at a time. We sort [5, 1, 4, 2, 3], processing the list left to right; everything left of the marker | is already in order, and each row shows the complete array after the current element has been inserted into its correct place.

The marker | moves one step right each row, and everything left of it is sorted. That is exactly what the code does.

Zoom in on the inner shifting for the single step i=3, where we insert key = 2 into the sorted front [1, 4, 5]:

The _ marks the moving gap. When we hit an element not larger than the key, we stop and drop the key into the gap.

Why insertion sort shines on nearly-sorted and small inputs

If the list is already sorted or almost sorted, the while loop almost never runs: each new element is already >= its left neighbor, so it stays put after one comparison. That makes insertion sort O(n) in the best case (one pass, no shifting). On a list that is off by only a few elements, the cost is roughly n plus the small number of shifts needed.

For small lists (say, fewer than 10-20 elements), insertion sort’s simplicity and low overhead often beat fancier O(n log n) sorts in practice. This is why high-performance sorting libraries switch to insertion sort for small sub-lists.

Stability

A sort is stable if elements that compare equal keep their original relative order. This matters when items carry extra data. Suppose you sort a list of (name, score) pairs by score; a stable sort keeps two people with the same score in the order they started, which lets you sort by one field and then another and get predictable results.

• Insertion sort: stable. It only moves an element past ones strictly greater (a[j] > key), never past an equal one.
• Bubble sort: stable. It only swaps on strictly greater-than (a[j] > a[j+1]), so equal neighbors never swap.
• Selection sort: not stable in its usual form. A long-distance swap can jump an element over an equal one. Example: sorting [3a, 3b, 1] by value swaps the first 3a with 1, giving [1, 3b, 3a] and reversing the two 3s.

Comparing the three

flowchart TD
    Start["Unsorted list of n elements"]
    Start --> B["Bubble sort:\nsweep neighbors,\nswap if out of order,\nlargest bubbles to the end"]
    Start --> S["Selection sort:\nscan for the minimum,\none swap per pass,\nput it at the front"]
    Start --> I["Insertion sort:\ngrow a sorted left region,\nslide each new element\nleftward into place"]
    B --> BR["O(n^2) time, O(1) space\nStable\nMany swaps"]
    S --> SR["O(n^2) time, O(1) space\nNot stable\nFewest swaps (n)"]
    I --> IR["O(n^2) worst, O(n) best\nO(1) space\nStable, great when nearly sorted"]

Deriving the O(n²) time and O(1) space

Time. Take the worst case for insertion sort: a reverse-sorted list like [5, 4, 3, 2, 1]. When we insert the element at index i, every one of the i elements to its left is larger, so the inner loop shifts all i of them. The total work is:

1 + 2 + 3 + ... + (n-1)

That sum equals n(n-1)/2. For large n the dominant term is n²/2, and Big-O drops constant factors, so this is O(n²). The same counting applies to bubble and selection sort: an outer loop of about n passes, each doing up to about n comparisons, gives roughly n × n = n² operations. In plain words: for every element you do work proportional to the whole list, and there are n elements, so cost grows with the square of the size. Double the input and the work roughly quadruples.

Space. All three sort in place. They use a fixed handful of extra variables (i, j, key, min_index, a temporary during a swap) no matter how large the list is. Extra memory does not grow with n, so the extra space is O(1) (constant).

Common pitfalls

• Off-by-one in the inner loop. In bubble sort you compare a[j] with a[j + 1], so j must stop at n - 2, i.e. use range(n - 1 - i). Looping to n - 1 and reading a[j + 1] would go past the end of the list and raise IndexError.
• Losing the value with a bad swap. Write a swap as a[i], a[j] = a[j], a[i]. Doing it in two steps, a[i] = a[j] then a[j] = a[i], overwrites the first value and copies it into both slots. Python’s tuple assignment avoids this because the right side is evaluated first.
• Forgetting to save key in insertion sort. You must copy a[i] into key before the shifting begins, because the shifting overwrites a[i]. Comparing against a[i] inside the loop after it has been overwritten gives wrong results.
• Assuming every sort is stable. If order among equal items matters, do not reach for selection sort. Test with duplicates.
• Sorting a copy by accident, or mutating when you did not mean to. These functions sort the list in place and change the caller’s list. If you need to keep the original, pass a copy: sorted_list = insertion_sort(original[:]). The [:] makes a shallow copy.

Practice

1. Rewrite insertion_sort to sort in descending order (largest first). Change exactly one comparison and re-run the trace on [5, 1, 4, 2, 3] in your head to confirm you get [5, 4, 3, 2, 1].
2. Add a counter to bubble_sort that counts how many swaps happen, and print it. Run it on an already-sorted list [1, 2, 3, 4] and on a reverse-sorted list [4, 3, 2, 1]. Explain the difference using the O(n²) derivation above.
3. Demonstrate that selection sort is not stable: sort a list of pairs like [(3, 'a'), (3, 'b'), (1, 'c')] by the first number using a selection sort you adapt, and show that 'a' and 'b' come out in a different relative order than they started.