Sorting Basics: Bubble, Selection and Insertion Sort

Why learn slow sorting algorithms

Python has sorted(). C++ has std::sort. You will almost never write a sorting algorithm at work.

You still learn these three, for good reasons. They are small enough to hold in your head completely. They teach the loop-and-swap patterns that appear in dozens of other problems. And exams ask about them. Understand them once, properly, and they stop being memorisation.

All three are comparison sorts: they work by comparing pairs of elements and moving them. All three are O(n^2) in the worst case. They differ in how they get there, and those differences matter.

Bubble sort

Idea: repeatedly walk through the list comparing neighbours, swapping them if they are out of order. After one full pass the largest element has "bubbled" to the end. After two passes the two largest are in place, and so on.

[5, 1, 4, 2]  compare 5 and 1 -> swap
[1, 5, 4, 2]  compare 5 and 4 -> swap
[1, 4, 5, 2]  compare 5 and 2 -> swap
[1, 4, 2, 5]  pass 1 done, 5 is settled at the end

def bubble_sort(arr):
    a = arr.copy()
    n = len(a)
    passes = 0

    for i in range(n - 1):
        swapped = False
        # last i elements are already in place
        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
        passes += 1
        if not swapped:          # already sorted, stop early
            break

    return a, passes

print(bubble_sort([5, 1, 4, 2, 8]))
print("Already sorted:", bubble_sort([1, 2, 3, 4, 5]))
print("Reverse sorted:", bubble_sort([5, 4, 3, 2, 1]))

The swapped flag is what makes bubble sort interesting. If a full pass makes no swaps, the list is sorted and we stop. On already-sorted input that is a single pass — O(n). Notice in the output that the sorted list needed one pass and the reversed list needed four.

Cost: O(n^2) worst and average, O(n) best (with the flag). O(1) extra space. It does a lot of swapping, which is why it is generally the slowest of the three in practice.

Selection sort

Idea: find the smallest element in the unsorted part and swap it into the front. Repeat with the remaining part.

[64, 25, 12, 22]  smallest is 12 -> swap with position 0
[12, 25, 64, 22]  smallest of the rest is 22 -> swap with position 1
[12, 22, 64, 25]  smallest of the rest is 25 -> swap with position 2
[12, 22, 25, 64]  done

def selection_sort(arr):
    a = arr.copy()
    n = len(a)
    swaps = 0

    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if a[j] < a[min_index]:
                min_index = j
        if min_index != i:
            a[i], a[min_index] = a[min_index], a[i]
            swaps += 1

    return a, swaps

print(selection_sort([64, 25, 12, 22, 11]))
print("Already sorted:", selection_sort([1, 2, 3, 4, 5]))

The distinctive feature: at most n-1 swaps, ever. It scans a lot but moves data very little. That makes it the right choice when writing is expensive relative to reading — for example on hardware where writes wear out the storage.

Cost: O(n^2) always, even on sorted input, because it always scans the remaining part fully to find the minimum. O(1) extra space.

Insertion sort

Idea: the way most people sort a hand of playing cards. Keep a sorted section on the left. Take the next element and slide it backwards until it sits in the right place.

[|5| 3, 8, 1]   5 alone is sorted
[|3, 5| 8, 1]   3 slides past 5
[|3, 5, 8| 1]   8 is already in place
[|1, 3, 5, 8|]  1 slides all the way to the front

def insertion_sort(arr):
    a = arr.copy()
    shifts = 0

    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # slide bigger elements one step right
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
            shifts += 1
        a[j + 1] = key

    return a, shifts

print(insertion_sort([5, 3, 8, 1, 9, 2]))
print("Already sorted:", insertion_sort([1, 2, 3, 4, 5, 6]))
print("Nearly sorted:", insertion_sort([1, 2, 4, 3, 5, 6]))

Look at the shift counts. Already-sorted input needs zero shifts. Nearly-sorted input needs one. This is insertion sort's real strength: on data that is already close to sorted, it runs in nearly O(n).

Cost: O(n^2) worst and average, O(n) best. O(1) extra space. Real sorting libraries switch to insertion sort for small chunks because its constant factor is low.

Stability

A sort is stable if elements with equal keys keep their original relative order.

Say you have students already sorted by name, and you now sort by marks. Two students both scored 85. A stable sort keeps them in name order. An unstable sort might swap them for no reason.

students = [("Aarav", 85), ("Bhavna", 92), ("Chetan", 85), ("Divya", 78)]

def insertion_sort_by_marks(data):
    a = list(data)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # strictly greater -> equal marks are never swapped -> stable
        while j >= 0 and a[j][1] > key[1]:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print("Original:", students)
print("Sorted by marks:", insertion_sort_by_marks(students))
print("Aarav still before Chetan - both scored 85, order preserved")

The comparison uses > and not >=. That one character is what makes it stable: equal elements never trigger a shift, so they never cross.

Selection sort is unstable in its standard swap-based form, because swapping a distant minimum into place can jump an equal element over another.

Which one when

Insertion sort — the default choice among the three. Best on small or nearly-sorted data, stable, simple.

Selection sort — when swapping is expensive and you want to guarantee few writes.

Bubble sort — mainly educational. It is easy to explain and the early-exit flag is a nice idea, but insertion sort beats it in almost every real case.

For anything of real size, use the library sort. Python's sorted() uses Timsort, which is O(n log n) and specifically exploits already-sorted stretches in the data.

Common mistakes

Getting the inner loop bounds wrong in bubble sort. Using range(n) instead of range(n - 1 - i) reads past the end and raises IndexError, or wastes time re-checking settled elements.

Swapping without a temporary in languages that need one. Python's a, b = b, a is safe. In C you must write temp = a; a = b; b = temp; — writing a = b; b = a; loses a value.

Claiming selection sort is O(n) on sorted input. It is not. It always does the full inner scan. Only bubble (with a flag) and insertion get a fast path.

Sorting a copy and forgetting to use it. In Python sorted(arr) returns a new list, while arr.sort() modifies in place and returns None. Writing arr = arr.sort() sets arr to None.

Using >= where you meant >. It quietly destroys stability without changing the sorted output, so tests on plain numbers will not catch it.

Practice

Try the sorting exercises on the practice page — trace each algorithm on paper for a 5-element list first.