Bubble Sort and Insertion Sort
Code both quadratic sorting algorithms, understand why they are O(n²), and recognise the one case where insertion sort beats merge sort.
Bubble Sort and Insertion Sort is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Study O(n²) Sorts?
Bubble sort and insertion sort are O(n²) in the worst case, making them impractical for large inputs. Yet every serious algorithm interview expects you to implement and analyse them. They teach fundamental concepts — comparison, swapping, stable sorting, and best-case behaviour — that apply to more advanced algorithms. Interviewers use them to test whether you can reason about loop invariants and asymptotic notation from first principles.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Bubble Sort: Bubble Up the Maximum
Bubble sort repeatedly scans the array and swaps adjacent elements that are out of order. After each full pass, the largest unsorted element 'bubbles up' to its final position at the end. After n-1 passes, the entire array is sorted. Its name comes from the way larger elements float upward like bubbles. It is the simplest sorting algorithm to describe but rarely used in practice.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Bubble Sort With Early Exit
An optimised bubble sort uses a swapped flag: if a full inner pass produces zero swaps, the array is already sorted and we exit early. This gives O(n) best case for already-sorted input — bubble sort's one genuine advantage. Without this flag, it always performs O(n²) comparisons. The early-exit optimisation is what interviewers check for when asking about bubble sort improvements.
def bubble_sort_optimised(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: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passBubble Sort Complexity Analysis
Bubble sort's outer loop runs n-1 times. The inner loop runs n-1-i times per pass: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 comparisons. This gives O(n²) average and worst case. With the early-exit flag, the best case drops to O(n) for sorted input. Space complexity is O(1) — only the swap requires a temporary swap of variables. Bubble sort is stable: equal elements maintain their relative order since we only swap strictly greater elements.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Insertion Sort: Building a Sorted Hand
Insertion sort mimics sorting a hand of cards: pick up the next card (element) and insert it into the correct position among the already-sorted cards to the left. The invariant is that arr[0:i] is always sorted. For each new element, shift larger elements rightward to make room. This in-place, stable algorithm has O(n²) worst case but O(n) best case for nearly-sorted data.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Insertion Sort Step by Step
Trace insertion sort on [3, 1, 4, 2]: i=1, key=1, shift 3 right → [1, 3, 4, 2]. i=2, key=4, no shifts → unchanged. i=3, key=2, shift 4 then 3 right → [1, 2, 3, 4]. Each element is compared with those to its left until we find its correct slot. The inner while loop performs the shifts using assignments (faster than swaps since one assignment per shift vs three for a swap).
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Insertion Sort on Nearly-Sorted Data
Insertion sort's killer feature is its O(n + inversions) complexity. An inversion is a pair (i,j) where i < j but arr[i] > arr[j]. For nearly-sorted arrays with only a few inversions, insertion sort is extremely fast — sometimes faster than merge sort in practice due to its simplicity and cache-friendly access pattern. Python's Timsort uses insertion sort on small subarrays for exactly this reason.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Stability in Sorting
A sorting algorithm is stable if equal elements maintain their original relative order after sorting. Both bubble sort and insertion sort are stable — they never swap equal elements. Stability matters when you sort by multiple keys sequentially: sort by secondary key first (stably), then sort by primary key (stably) to maintain secondary-key order among ties. Merge sort is also stable; heap sort and quick sort are generally not.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableInsertion Sort as Binary Search
The inner loop of insertion sort both finds the correct position and shifts elements. You can use binary search to find the position in O(log i) comparisons, but shifts still take O(i) time — so the overall complexity remains O(n²). The optimisation reduces comparisons (useful for expensive comparison functions) but not total operations. This 'binary insertion sort' appears in Timsort for small chunk sizes.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Bubble vs Insertion: When to Use Each
In interviews, state this comparison confidently: insertion sort is strictly better than bubble sort — both are O(n²) worst case and O(1) space, but insertion sort makes fewer writes (O(n+k) for k inversions vs O(n²) for bubble), is more cache-friendly, and is the practical choice for small n (Timsort uses it). Bubble sort's only real advantage is pedagogical simplicity. In production, always use the language's built-in sort.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Counting Inversions as a Metric
The number of inversions in an array equals the number of pairs (i,j) where i < j but arr[i] > arr[j]. Insertion sort performs exactly as many shifts as there are inversions — a useful insight. Counting inversions efficiently (O(n log n)) requires a modified merge sort. Interviewers sometimes ask 'how inversions-aware is your algorithm?' as a follow-up to sorting discussions.
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: bubble sort makes n-1 passes, each bubbling the current maximum to its final position, with O(n²) worst case but O(n) best case with the early-exit flag, insertion sort shifts elements rightward to insert the current key in the correct sorted position, running in O(n + inversions) time making it optimal for nearly-sorted data, and both algorithms are stable, O(1) space, and O(n²) worst case — but insertion sort is strictly preferred over bubble sort in all practical scenarios. Next up we implement merge sort from scratch.
Frequently asked questions
Is the “Bubble Sort and Insertion Sort” lesson free?
Yes — the full text of “Bubble Sort and Insertion Sort” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Bubble Sort and Insertion Sort”?
Code both quadratic sorting algorithms, understand why they are O(n²), and recognise the one case where insertion sort beats merge sort. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Bubble Sort and Insertion Sort” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Bubble Sort and Insertion Sort
- Merge Sort: Divide, Sort, Merge
- Quick Sort and Pivot Selection
- Non-Comparison Sorts and Python's sort()