Bubble, Selection and Insertion Sort: Time Complexity and Why Insertion Sort Wins on Nearly Sorted Data

By 0xmote · May 25, 2026 · 24 min read · Updated Sep 29, 2026 Beginner Tutorial

Key takeaways

The three O(n^2) sorts are rarely used on large inputs, but they teach the swap, select and shift ideas behind faster algorithms. Each gets a step-by-step implementation and complexity analysis, then a comparison of when each still makes sense and how Python's built-in sort behaves.

Introduction

Sorting is the most fundamental algorithm. It’s the best topic for learning time complexity analysis and optimization.

You will almost never write bubble, selection or insertion sort in production; list.sort() is faster than anything you would hand-write in Python. They are still worth learning for three concrete reasons. First, each one embodies an idea that reappears in faster algorithms: swapping neighbours (bubble), repeatedly selecting the extreme (selection, which becomes heapsort once the selection uses a heap), and inserting into a sorted prefix (insertion, which Timsort and introsort still use for small ranges). Second, they are small enough to trace by hand, which makes them the best practice ground for counting comparisons and swaps and reasoning about best, average and worst cases. Third, interviewers use them to test loop boundaries and invariants, and the off-by-one mistakes people make in these ten-line functions are the same ones that break binary search and two-pointer code later.

A useful way to read each section is to ask: what is the invariant after each pass of the outer loop? Once you can state it, the algorithm’s correctness and its complexity both follow.

Bubble Sort

Algorithm

Compare adjacent elements and move larger values to the right:

[5, 2, 4, 1, 3]
 ↓ Compare & swap
[2, 5, 4, 1, 3]
    ↓
[2, 4, 5, 1, 3]
       ↓
[2, 4, 1, 5, 3]
          ↓
[2, 4, 1, 3, 5]  ← 5 in place

Python Implementation

Compare adjacent cells and swap if left is larger. Each pass “bubbles up” the largest value in the unsorted range to the right end.

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        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
        
        # Already sorted if no swaps
        if not swapped:
            break
    
    return arr
# Test
arr = [5, 2, 4, 1, 3]
print(bubble_sort(arr))  # [1, 2, 3, 4, 5]

The invariant is: after pass i, the last i + 1 positions hold the largest elements in their final order. That is why the inner loop runs to n - 1 - i instead of n - 1; the tail is already done, and comparing into it would waste work. Getting that bound wrong in the other direction, range(n - i), makes arr[j + 1] read one past the end and raises IndexError: list index out of range on the first pass.

The swapped flag is what gives bubble sort its O(n) best case. Without it, the function always performs all n(n−1)/2 comparisons even on sorted input. With it, a pass that makes no swaps proves the array is sorted and the loop stops. Note that the function sorts in place and also returns the same list object; arr and the return value are the same list, which surprises people who expect it to behave like sorted().

Bubble sort’s real weakness is the number of swaps: every inversion (a pair out of order) costs one swap, and a reversed array has n(n−1)/2 of them. Small elements near the end also move left only one position per pass (the “turtles” problem), which is why variants such as cocktail shaker sort, which alternates direction, were invented.

Time Complexity

Best: O(n) (already sorted)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: Yes Step-by-Step Trace:

[5, 2, 4, 1, 3]
Pass 1:
[2, 5, 4, 1, 3]
[2, 4, 5, 1, 3]
[2, 4, 1, 5, 3]
[2, 4, 1, 3, 5] ← 5 in place
Pass 2:
[2, 4, 1, 3, 5]
[2, 1, 4, 3, 5]
[2, 1, 3, 4, 5] ← 4 in place
Pass 3:
[1, 2, 3, 4, 5] ← 3 in place
Pass 4: No swaps → Done

Selection Sort

Algorithm

Find minimum and swap with front:

[5, 2, 4, 1, 3]
 ↓ Find min: 1
[1, 2, 4, 5, 3]  ← 1 in place
    ↓ Find min: 2
[1, 2, 4, 5, 3]  ← 2 in place
       ↓ Find min: 3
[1, 2, 3, 5, 4]  ← 3 in place
          ↓
[1, 2, 3, 4, 5]  ← Done

Python Implementation

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        # Find minimum after i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr
# Test
arr = [5, 2, 4, 1, 3]
print(selection_sort(arr))  # [1, 2, 3, 4, 5]

The invariant is: after iteration i, arr[0..i] holds the i + 1 smallest elements in sorted order. Selection sort always scans the entire unsorted suffix to find the minimum, and it has no way to notice that the input is already sorted, so it performs exactly n(n−1)/2 comparisons on every input. That is why its best case is O(n²) too.

What it does minimize is writes: at most n − 1 swaps, one per position, regardless of the input. That matters in the rare situation where writing is far more expensive than reading, for example sorting records on flash memory with limited write endurance, or when each “swap” moves a large physical object. When min_idx == i the swap is a no-op; adding if min_idx != i: avoids the write, which is only worth doing if writes are genuinely expensive. For in-memory Python lists, selection sort is simply the slowest of the three on almost every input.

Time Complexity

Best: O(n²)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: No Why Not Stable?

[5a, 5b, 2]
Step 1: Find min (2), swap with 5a
[2, 5b, 5a]  ← 5b now before 5a (order changed!)
Selection sort can change relative order of equal elements

The long-distance swap is the culprit: moving the minimum to the front throws the displaced element somewhere far away, possibly past another element with the same key. Stability matters whenever you sort by one field after sorting by another. If you sort an order list by date and then, with a stable sort, by customer, each customer’s orders stay in date order. With an unstable sort, that earlier ordering is lost. Selection sort can be made stable by shifting elements right instead of swapping (effectively turning it into an insertion step), at the cost of more writes.

Insertion Sort

Algorithm

Insert into sorted portion:

[5, 2, 4, 1, 3]
[5] 2 4 1 3  ← 5 is sorted
[2, 5] 4 1 3  ← Insert 2
[2, 4, 5] 1 3  ← Insert 4
[1, 2, 4, 5] 3  ← Insert 1
[1, 2, 3, 4, 5]  ← Insert 3

Python Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Move elements larger than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr
# Test
arr = [5, 2, 4, 1, 3]
print(insertion_sort(arr))  # [1, 2, 3, 4, 5]

The invariant is: before iteration i, arr[0..i-1] is sorted (but, unlike selection sort, not necessarily in its final positions). Each step takes arr[i] out as key, shifts every larger element in the sorted prefix one slot right, and drops key into the gap. Using shifts rather than swaps means each move is one write instead of three, which is why insertion sort is noticeably faster than bubble sort in practice even though both are O(n²).

The two conditions in while j >= 0 and arr[j] > key are both essential. j >= 0 stops at the front of the list; if you drop it, j becomes −1 and Python’s negative indexing silently reads the last element instead of raising an error, which produces wrong results rather than a crash. Using > rather than >= is what makes the sort stable: an equal element already in the prefix is not shifted, so the new element lands after it. Change it to >= and the sort still works but equal keys come out in reverse input order, a bug that is invisible when you test with plain integers.

Time Complexity

Best: O(n) (already sorted)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: Yes Step-by-Step Trace:

[5, 2, 4, 1, 3]
i=1, key=2:
  [5, 5, 4, 1, 3]  (shift 5)
  [2, 5, 4, 1, 3]  (insert 2)
i=2, key=4:
  [2, 5, 5, 1, 3]  (shift 5)
  [2, 4, 5, 1, 3]  (insert 4)
i=3, key=1:
  [2, 4, 5, 5, 3]  (shift 5)
  [2, 4, 4, 5, 3]  (shift 4)
  [2, 2, 4, 5, 3]  (shift 2)
  [1, 2, 4, 5, 3]  (insert 1)
i=4, key=3:
  [1, 2, 4, 5, 5]  (shift 5)
  [1, 2, 4, 4, 5]  (shift 4)
  [1, 2, 3, 4, 5]  (insert 3)

Count the shifts in this trace: 1, 1, 3 and 2, seven in total. That number is exactly the number of inversions in the input [5, 2, 4, 1, 3] (pairs that are out of order), and it is the key to insertion sort’s behaviour: the running time is O(n + inversions). A sorted array has zero inversions, so the sort does one comparison per element and finishes in O(n). A reversed array has the maximum, n(n−1)/2, giving the O(n²) worst case. Data where each element is at most k positions from its final place has at most about n·k inversions, so insertion sort handles it in O(n·k), which for small k beats any O(n log n) algorithm.

That property, combined with a very tight inner loop and no recursion, is why insertion sort survives inside every major production sort. Timsort uses it to extend short runs to a minimum length before merging; C++ standard library implementations of std::sort switch to insertion sort once a partition falls below roughly 16 elements. It is also the natural choice for online sorting, where elements arrive one at a time and the list must stay sorted after each insertion; Python’s bisect.insort does exactly this, with a binary search for the position and a single shift.

Sorting Comparison

Algorithm	Best	Average	Worst	Space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No

Big-O hides constants that matter a lot at small sizes. On a list of 10 or 20 elements, insertion sort usually beats merge sort and quicksort, because it has no recursion, no extra memory and a very predictable memory access pattern. Somewhere in the tens to low hundreds of elements, depending on the machine and language, the O(n log n) algorithms take over, and by n = 10,000 the difference is dramatic: n² is 100 million operations while n log n is roughly 130,000. In Python, where each comparison is an interpreted operation, a hand-written O(n²) sort on 10,000 elements takes seconds, while the built-in sort finishes in a few milliseconds.

The quicksort row deserves a footnote. Its O(n²) worst case is not theoretical; a naive “first element as pivot” quicksort hits it on already sorted input, which is a very common real-world case. Production implementations avoid it with median-of-three or random pivots, and introsort switches to heapsort if recursion gets too deep, guaranteeing O(n log n).

When to Use Each

# Bubble Sort
# - Educational purposes
# - Nearly sorted arrays (with early termination)
# Selection Sort
# - Minimize number of swaps
# - Small arrays
# Insertion Sort
# - Nearly sorted arrays (best case O(n))
# - Small arrays
# - Online sorting (elements arrive one at a time)
# Quick/Merge/Heap Sort
# - Large arrays
# - Need O(n log n) performance

Python Built-in Sorting

sorted() vs sort()

# sorted(): Returns new list
arr = [5, 2, 4, 1, 3]
sorted_arr = sorted(arr)
print(arr)  # [5, 2, 4, 1, 3] (original preserved)
print(sorted_arr)  # [1, 2, 3, 4, 5]
# sort(): In-place sorting
arr = [5, 2, 4, 1, 3]
arr.sort()
print(arr)  # [1, 2, 3, 4, 5] (original modified)
# Reverse
arr.sort(reverse=True)
print(arr)  # [5, 4, 3, 2, 1]
# Custom key
students = [('Alice', 85), ('Bob', 90), ('Charlie', 80)]
students.sort(key=lambda x: x[1], reverse=True)
print(students)  # [('Bob', 90), ('Alice', 85), ('Charlie', 80)]

The difference between sorted() and .sort() is easy to get wrong in one specific way: arr.sort() returns None. Writing arr = arr.sort() replaces the list with None, and the error only appears later, as TypeError: 'NoneType' object is not subscriptable. sorted() works on any iterable (tuples, dict keys, generators) and always returns a new list; .sort() exists only on lists and modifies them in place.

The key function is called once per element, and the results are cached, so an expensive key such as len or str.lower costs n calls, not n log n. That makes key both faster and simpler than the old comparison-function style, which Python 3 removed from sort() (use functools.cmp_to_key if you have a legacy comparator). reverse=True keeps the sort stable: equal elements stay in input order, which is not the same as sorting ascending and then calling .reverse(), since reversing flips the order of ties too.

Timsort (Python’s Default)

# Python uses Timsort (hybrid of merge + insertion)
# - Time: O(n log n) worst case
# - Space: O(n)
# - Stable: Yes
# - Optimized for real-world data
arr = [5, 2, 4, 1, 3]
arr.sort()  # Uses Timsort

Timsort, written by Tim Peters for Python in 2002, is built on the observation that real data is rarely random: it tends to contain runs, stretches that are already ascending or descending. Timsort scans for those runs, reverses descending ones, extends short runs to a minimum length with insertion sort, and then merges runs with a strategy that keeps merges balanced. On random data it behaves like a well-tuned merge sort. On data that is already sorted or made of a few sorted chunks (appending new records to a sorted list, concatenating two sorted lists) it approaches O(n). It is also used by Java for sorting objects and by several other languages.

Since Python 3.11, the merge policy is “powersort”, a refinement with better provable balance; the behaviour you rely on, O(n log n) worst case, stability and fast handling of presorted runs, is unchanged. The O(n) extra space is for the merge buffer and is the main trade-off versus an in-place algorithm such as heapsort.

Where sorting goes wrong in real Python code

Ties that must keep input order

When equal scores must preserve original input order, you need a stable sort such as insertion sort, merge sort or Timsort. Below is a pattern for sorting by (score descending, original index ascending).

from dataclasses import dataclass
@dataclass
class Row:
    name: str
    score: int
rows = [
    Row("A", 90),
    Row("B", 90),
    Row("C", 80),
]
# Python's sort is stable, so use index as secondary key
indexed = list(enumerate(rows))
indexed.sort(key=lambda t: (-t[1].score, t[0]))
ordered = [r for _, r in indexed]
print([r.name for r in ordered])  # ['A', 'B', 'C']

Because Python’s sort is already stable, the index here is technically redundant: rows.sort(key=lambda r: -r.score) produces the same order. Adding the original index as an explicit tie-breaker is still a useful habit in two situations. It documents the intent (“ties keep input order”) in the key itself, and it keeps the result correct if the data is later sorted by code that is not stable, such as a database ORDER BY without a unique column, heapq, or a C++ std::sort. The -t[1].score trick for descending order only works for numbers; to sort strings descending while keeping another key ascending, sort twice using stability (secondary key first, then primary key with reverse=True).

NaN silently breaks the ordering

Ordinary floats sort correctly; the real danger is NaN. NaN compares false with everything, including itself, so it breaks the assumption every sort makes that for any two elements one is less than, greater than, or equal to the other. sorted([3.0, float('nan'), 1.0, 2.0]) does not raise an error; it returns a list that is not fully sorted, and the exact result depends on where the NaN started. Filter or replace NaN before sorting, or use a key such as lambda x: (math.isnan(x), x) to push them to the end. The separate issue that 0.1 + 0.2 != 0.3 affects equality checks, not ordering.

Sorting inside a loop, and full sorts for top-k

With n up to about 10³, a hand-written O(n²) sort is fine; with n = 10⁵ or more, it is 10¹⁰ operations and will time out. A more common timeout in Python solutions is not a hand-written bubble sort but calling sort() inside a loop, for example re-sorting a list after every insertion, which turns an O(n log n) solution into O(n² log n). Keeping the list sorted with bisect.insort or using a heap is usually the fix. Similarly, if you only need the k smallest elements, heapq.nsmallest(k, arr) runs in O(n log k) instead of sorting everything; for k close to n, a plain sorted(arr)[:k] is just as good.

When a quadratic sort is still the right choice

Sort	Best	Average	Worst	When to Use
Bubble	O(n)	O(n²)	O(n²)	Nearly sorted
Selection	O(n²)	O(n²)	O(n²)	Minimize swaps
Insertion	O(n)	O(n²)	O(n²)	Nearly sorted, small arrays

Of the three, insertion sort is the one that survives in real code. Its inner loop does almost nothing when the input is already close to sorted, and on very small arrays its low overhead beats the bookkeeping of merge or quick sort, which is why production hybrids such as Timsort and introsort switch to insertion sort for short runs. Selection sort has one niche: it performs at most n − 1 swaps, which matters only when writing an element is far more expensive than comparing two. Bubble sort has no case where it beats insertion sort, so treat it as a teaching tool.

In interviews and application code, call sort() or sorted() unless the problem explicitly asks you to implement the algorithm. Next: Advanced Sorting (Quick/Merge/Heap).

Frequently Asked Questions (FAQ)

Q. Why can insertion sort beat O(n log n) sorts on nearly sorted data?

A. Insertion sort’s inner loop stops as soon as the element reaches its place, so its running time is O(n + number of inversions). On input that is already almost sorted there are few inversions and it runs close to O(n) with very low overhead. That is why hybrid sorts such as Timsort use insertion sort for small runs.

Key takeaways

Introduction

Bubble Sort

Algorithm

Python Implementation

Time Complexity

Selection Sort

Algorithm

Python Implementation

Time Complexity

Insertion Sort

Algorithm

Python Implementation

Time Complexity

Sorting Comparison

When to Use Each

Python Built-in Sorting

sorted() vs sort()

Timsort (Python’s Default)

Where sorting goes wrong in real Python code

Ties that must keep input order

NaN silently breaks the ordering

Sorting inside a loop, and full sorts for top-k

When a quadratic sort is still the right choice

Related Articles

Frequently Asked Questions (FAQ)

Q. Why can insertion sort beat O(n log n) sorts on nearly sorted data?