Sorting Algorithms: Bubble, Selection, Insertion, and Beyond

Your class teacher has just finished checking six answer scripts for a unit test. The marks, in the order the scripts happen to be stacked, are: 72, 55, 91, 60, 48, 83. Before these can go into the mark register or be used to prepare a merit list, they need to be arranged from lowest to highest (or highest to lowest). You have almost certainly done this yourself while updating a scoreboard, arranging playing cards, or checking an IRCTC waitlist that keeps shuffling as people cancel tickets. The moment you try to actually do it — not just glance at the numbers and "know" the order, but produce a step-by-step method a friend with no number sense could follow — you are inventing a sorting algorithm. This chapter formalizes three such methods that a person would naturally invent, traces each one number-by-number so you can see exactly why it works, and then explains why, for very large amounts of data, none of the three is good enough.

What sorting actually means

A list of values is sorted in ascending order if every element is less than or equal to the element right after it. [48, 55, 60, 72, 83, 91] is sorted; [72, 55, 91, 60, 48, 83] is not, because 72 is followed by 55. A sorting algorithm is a precise sequence of comparisons and swaps that takes any starting arrangement and produces the sorted one. The three algorithms in this chapter differ only in which pair of elements they compare next and when they decide to swap — the comparison itself, "is this value bigger than that one?", never changes. Keeping that in mind will help you tell the three apart, because on paper their code looks deceptively similar.

Sorting is not restricted to numbers. A merit list is sorted by marks, a phone contact list is sorted alphabetically by name, a train timetable is sorted by departure time, and a cricket scorecard is sorted by runs scored. Everywhere in this chapter, "compare two elements" simply means "decide which one should come first," whatever the underlying data is.

Bubble sort: repeatedly compare and swap neighbours

Picture six students standing in a line by height, in a random order, and imagine you can only ever compare two students who are standing next to each other, swapping them if the one on the left is taller than the one on the right. If you walk once from the left end to the right end of the line, performing this neighbour-swap at every step, what happens to the tallest student in the line? Every time the tallest student is compared against a neighbour, that neighbour is shorter, so the tallest student always wins the comparison and moves one position to the right. By the time your walk reaches the end of the line, the tallest student has been pushed, comparison by comparison, all the way to the last position. That is the entire idea of bubble sort: one full left-to-right sweep guarantees that the largest remaining value "bubbles" up to its correct final position at the end of the unsorted portion, the same way an air bubble rises to the top of a glass of water one step at a time.

Doing one sweep is not enough to sort the whole line, because the second-tallest, third-tallest, and so on have only moved a little closer to their correct spots, not all the way. So bubble sort repeats the sweep, each time over a slightly shorter stretch (since the tail end is already correctly settled), until no swap is needed in an entire sweep — at which point the whole list must be sorted.

Let's trace it precisely on [5, 2, 4, 6, 1, 3], comparing index j with index j+1 and swapping when the left value is bigger:

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

print(bubble_sort([5, 2, 4, 6, 1, 3]))

Pass 1 (comparing indices 0-1, 1-2, 2-3, 3-4, 4-5 in order), starting from [5, 2, 4, 6, 1, 3]:

• Compare 5 and 2 → 5 > 2, swap → [2, 5, 4, 6, 1, 3]
• Compare 5 and 4 → 5 > 4, swap → [2, 4, 5, 6, 1, 3]
• Compare 5 and 6 → 5 < 6, no swap → [2, 4, 5, 6, 1, 3]
• Compare 6 and 1 → 6 > 1, swap → [2, 4, 5, 1, 6, 3]
• Compare 6 and 3 → 6 > 3, swap → [2, 4, 5, 1, 3, 6]

Notice exactly what the height-line analogy predicted: the largest value, 6, started at index 3 and, through three consecutive swaps, walked all the way to index 5 — its final, correct position — in a single pass. Nothing else is guaranteed to be in its final position yet.

Pass 2 only needs to sweep indices 0 through 4 (index 5 is settled): [2, 4, 5, 1, 3, 6] becomes [2, 4, 1, 3, 5, 6] — the second-largest remaining value, 5, bubbles to index 4.

Pass 3 sweeps indices 0 through 3: [2, 4, 1, 3, 5, 6] becomes [2, 1, 3, 4, 5, 6].

Pass 4 sweeps indices 0 through 2: [2, 1, 3, 4, 5, 6] becomes [1, 2, 3, 4, 5, 6].

Pass 5 sweeps index 0 alone, finds 1 < 2, makes no swap, so swapped stays False and the loop breaks early. Final output: [1, 2, 3, 4, 5, 6].

Common misconception: many students describe bubble sort as "comparing every pair of numbers in the list." That is what selection sort effectively scans for (see below), not bubble sort. Bubble sort only ever compares elements that are immediately next to each other at that moment. A value that needs to move five positions to the left cannot jump there in one step — it has to be swapped one position at a time across several passes. This is precisely why bubble sort can need up to n - 1 passes in the worst case: information about "where the smallest element belongs" can only travel one step per pass when it is moving in the direction opposite to the sweep.

Selection sort: repeatedly find the minimum and place it

Now imagine a different, equally natural strategy: to fill the first position of the sorted line, scan the entire unsorted group, find whichever student is shortest, and swap that student into the first position. Then scan the remaining unsorted group (everyone except position 0) for the next shortest, and place them at position 1. Repeat. This is selection sort — at each step it selects the minimum of what remains and fixes it in place.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(selection_sort([5, 2, 4, 6, 1, 3]))

Tracing on the same array [5, 2, 4, 6, 1, 3]:

• i = 0: scan indices 0-5 for the minimum. Values are 5, 2, 4, 6, 1, 3 — the minimum is 1 at index 4. Swap index 0 and index 4 → [1, 2, 4, 6, 5, 3]
• i = 1: scan indices 1-5: 2, 4, 6, 5, 3 — the minimum is 2, already at index 1. Swap with itself → [1, 2, 4, 6, 5, 3] (unchanged)
• i = 2: scan indices 2-5: 4, 6, 5, 3 — the minimum is 3 at index 5. Swap index 2 and index 5 → [1, 2, 3, 6, 5, 4]
• i = 3: scan indices 3-5: 6, 5, 4 — the minimum is 4 at index 5. Swap index 3 and index 5 → [1, 2, 3, 4, 5, 6]
• i = 4: scan indices 4-5: 5, 6 — the minimum is 5, already at index 4. Swap with itself → [1, 2, 3, 4, 5, 6]

Final output: [1, 2, 3, 4, 5, 6], matching bubble sort — both are correct, but they clearly reach the answer through completely different sequences of comparisons.

Common misconception, corrected with numbers: students often assume every quadratic sorting algorithm behaves the same way on nice, already-sorted input. It does not. Feed the already-sorted array [1, 2, 3, 4, 5, 6] into selection sort: at i = 0 it still scans all 5 remaining elements to confirm 1 is the minimum, at i = 1 it scans the remaining 4 to confirm 2 is the minimum, and so on — it makes exactly 5 + 4 + 3 + 2 + 1 = 15 comparisons whether the input was already sorted or completely scrambled, because the inner loop has no way to know the array is sorted without checking. Bubble sort, by contrast, would finish that same sorted array in a single pass of 5 comparisons and zero swaps, because the swapped flag lets it detect "no work happened" and stop. Selection sort's comparison count is fixed by n alone; bubble and insertion sort's comparison count depends on how disordered the input already is.

What selection sort does win on is swaps: it performs at most one swap per outer step, so at most n - 1 swaps total — here, only 3 actual swaps happened (i = 0, 2, 3) out of 5 outer steps. Bubble sort, in the same run, performed 4 swaps in pass 1 alone. If each "element" is not a single number but an entire large student record that is expensive to move in memory, minimizing swaps can matter more than minimizing comparisons.

Insertion sort: build up a sorted portion, one item at a time

The third natural strategy is how most people actually sort a hand of playing cards. You hold the first card — trivially "sorted" by itself. You pick up the second card and slide it into its correct position relative to the first, either before or after it. You pick up the third card and slide it leftward past any card bigger than it, stopping as soon as you hit a card that is smaller or reach the start of your hand. At every stage, the cards in your hand (to the left of the card you're currently placing) are fully sorted among themselves; you are simply growing that sorted region by one card at a time.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))

Tracing on [5, 2, 4, 6, 1, 3], where key is the card currently being placed:

• i = 1, key = 2: compare with arr[0] = 5. 5 > 2, so shift 5 right. No more elements to the left. Insert 2 at index 0 → [2, 5, 4, 6, 1, 3]
• i = 2, key = 4: compare with arr[1] = 5. 5 > 4, shift 5 right. Compare with arr[0] = 2. 2 is not > 4, stop. Insert 4 at index 1 → [2, 4, 5, 6, 1, 3]
• i = 3, key = 6: compare with arr[2] = 5. 5 is not > 6, stop immediately. Insert 6 back at index 3 → [2, 4, 5, 6, 1, 3] (unchanged)
• i = 4, key = 1: compare with 6, 5, 4, 2 in turn — all are greater than 1, so all four shift right one step. Insert 1 at index 0 → [1, 2, 4, 5, 6, 3]
• i = 5, key = 3: compare with 6, 5, 4 — all greater, shift right. Compare with 2 — not greater, stop. Insert 3 at index 2 → [1, 2, 3, 4, 5, 6]

Final output: [1, 2, 3, 4, 5, 6], again matching the other two.

Insertion sort's best case reveals something the other two cannot match as cleanly: run it on the already-sorted [1, 2, 3, 4, 5, 6]. At every value of i, the very first comparison (arr[j] > key) is false, since each element is already smaller than nothing to its left needs moving, so the while loop body never executes. That is exactly n - 1 = 5 comparisons and zero shifts for the whole array — genuinely proportional to n, not n squared. This is why insertion sort is the algorithm real programming language libraries fall back on for small or nearly-sorted chunks of data: Python's built-in sorted() and list.sort() use an algorithm called Timsort, which is fundamentally a merge sort (described below) that switches to plain insertion sort whenever it is working on a small enough run of elements, because insertion sort is genuinely faster than fancier algorithms once the run is small or close to sorted already.

Comparing the three honestly

Algorithm        Worst-case      Best-case        Extra memory   Stable?
Bubble sort       n(n-1)/2         n - 1             none          yes
                  comparisons      comparisons
                  (scrambled       (already
                  input)           sorted, with
                                   the swapped-
                                   flag check)

Selection sort    n(n-1)/2         n(n-1)/2          none          no
                  comparisons,     comparisons
                  always,          always -
                  input order      does not
                  irrelevant       adapt

Insertion sort    n(n-1)/2         n - 1             none          yes
                  comparisons      comparisons
                  (reverse-        (already
                  sorted input)    sorted input)

"Stable" needs unpacking, and it is where selection sort quietly misbehaves in a way that matters for real ranking problems. A sort is stable if, whenever two elements are equal, their original relative order is preserved in the output. Suppose a merit list must be sorted by total marks, but two students, P and Q, both scored 5 marks, with P listed before Q in the original roll-number order — and the school wants ties broken by roll number, i.e. P should still appear before Q. Watch what selection sort does to [(5, "P"), (5, "Q"), (3, "R")]:

• i = 0: scanning all three, the minimum mark is 3, belonging to R at index 2. Swap index 0 and index 2 → [(3, "R"), (5, "Q"), (5, "P")]
• i = 1: scanning indices 1-2, both have mark 5; since Q's mark is not strictly less than P's, the minimum stays at index 1 (Q). No swap.

Final result: [(3, "R"), (5, "Q"), (5, "P")] — Q now comes before P, even though P was listed first originally. The long-distance swap in step 1 silently reversed their order. Bubble sort and insertion sort never do this, because both only ever move an element past a neighbour that is strictly greater (or smaller); equal elements are simply never swapped past each other, so their original order survives untouched. When you need a "sort by this, but break ties by whatever order they were already in," bubble sort or insertion sort give you that for free; selection sort does not.

Beyond O(n²): why these three are not enough for big data

All three algorithms above do roughly n(n-1)/2 comparisons in the worst case — a number that grows proportional to n squared as the list grows. For the 6-element examples in this chapter that is at most 15 comparisons, unnoticeable. But real systems sort far more than 6 items: an IRCTC waitlist during a festival rush can have tens of thousands of PNR entries to reorder by booking timestamp; a bank's UPI transaction log for one day can run into millions of records. Watch how badly n² scales:

n          comparisons for an n^2 sort   comparisons for an n log n sort
10                    ~45                          ~33
100                 ~4,950                         ~664
1,000              ~499,500                       ~9,966
100,000      ~4,999,950,000                    ~1,660,964

At 100,000 records, a quadratic algorithm needs roughly 5 billion comparisons; an algorithm whose comparison count grows like n log n instead needs under 2 million — more than 3,000 times fewer. This gap is why computer scientists invented divide-and-conquer sorting algorithms such as merge sort and quicksort, which you will study in full detail in later chapters. The core idea behind merge sort, briefly: split the list in half, recursively sort each half (using the exact same procedure), then merge the two already-sorted halves back together by repeatedly comparing their front elements and taking the smaller one — a merge step that only needs to look at each element once. Splitting a list of size n in half repeatedly takes about log₂ n levels of splitting (for n = 100,000, that is only about 17 levels, since 2 raised to the 17th power already exceeds 100,000), and each level does about n total work to merge everything back — giving the n log n total from the table above.

None of this makes bubble, selection, and insertion sort obsolete. Insertion sort, as you saw, is genuinely the fastest simple option when data is already nearly sorted or when there are only a handful of elements — which is exactly why production sorting libraries, including Python's Timsort, still use it as a building block. Selection sort remains the right choice when swapping elements is far more expensive than comparing them. Bubble sort is mainly taught for what it makes visible: it is the clearest possible demonstration of how a sequence of small, local swaps can eventually produce global order, and the "swapped" early-exit trick is a first, gentle introduction to the general idea that an algorithm should recognize when its job is already done.

Practice: active recall

1. Trace bubble sort on [9, 3, 7, 1]. Write out the array after every single swap, and state which pass each swap belongs to.
2. How many comparisons will selection sort make while sorting a list of 7 elements, regardless of their starting order? Show the arithmetic.
3. An array is already sorted: [10, 20, 30, 40]. How many comparisons does insertion sort make on it? How many does bubble sort (with the swapped-flag optimization) make? Explain why the two numbers come out equal here.
4. Is insertion sort stable? Using the pair list [(4, "A"), (4, "B"), (2, "C")] sorted by the first value, trace insertion sort step by step and confirm whether A still appears before B in the output.
5. A program needs to sort a list of 50 very large data records where each swap involves copying a huge amount of memory, but comparing two records is cheap. Which of the three algorithms in this chapter minimizes the number of swaps, and why?
6. A company needs to sort 2,000,000 UPI transaction records by timestamp. Using the growth numbers in the "Beyond O(n²)" section, explain in your own words why none of bubble, selection, or insertion sort would be an acceptable choice here, even though all three are completely correct algorithms.

Answer key (brief): (1) Pass 1: compare 9,3 → swap → [3,9,7,1]; compare 9,7 → swap → [3,7,9,1]; compare 9,1 → swap → [3,7,1,9]. Pass 2: compare 3,7 → no swap; compare 7,1 → swap → [3,1,7,9]. Pass 3: compare 3,1 → swap → [1,3,7,9], sorted. (2) 6+5+4+3+2+1 = 21 comparisons, always, since selection sort's inner loop always runs fully regardless of input order. (3) Both make exactly 3 comparisons (n−1, since n=4) and zero swaps, because on already-sorted input every single adjacent/neighbour comparison in both algorithms comes out false on the first try. (4) Yes, stable: i=1, key=4 (B), compare with arr[0]=4 (A) — 4 is not strictly greater than 4, so no shift occurs and B is inserted right after A; A stays before B in the output, exactly as the "equal values are never shifted past" rule predicts. (5) Selection sort, because it performs at most one swap per outer iteration (at most 49 swaps for 50 elements), while bubble sort can perform many more swaps per pass and insertion sort can shift many elements for each insertion. (6) At n = 2,000,000, an n² algorithm needs on the order of two trillion comparisons versus roughly 42 million for an n log n algorithm — a gap of many orders of magnitude that turns a sort taking a couple of seconds into one that could take hours or days, even though bubble, selection, and insertion sort would all eventually produce the exact right answer.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind sorting algorithms: bubble, selection, insertion, and beyond, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.