What is Bubble Sort?
Learn how bubble sort works, its O(n²) complexity, the O(n) early-exit optimization, and how to answer this interview question.
Expected Interview Answer
Bubble sort repeatedly steps through an array comparing each pair of adjacent elements and swapping them if they are out of order, so on every full pass the largest remaining unsorted element "bubbles up" to its correct position at the end, giving an O(n²) sort with an O(n) best case when an early-exit flag detects the array is already sorted.
Each pass scans from the start to the current unsorted boundary, swapping any adjacent pair that is out of order, which guarantees the single largest element in the unsorted range reaches its final position by the end of that pass. Without an optimization, this repeats for n-1 passes regardless of input order, giving O(n²) comparisons and swaps in the average and worst case. A simple but important optimization tracks whether any swap occurred during a pass; if none did, the array is already sorted and the algorithm exits early, giving O(n) best case on already-sorted input. Because a swap only happens when the left element is strictly greater than the right, equal elements are never swapped past each other, making bubble sort stable — but it is rarely used in production due to being consistently slower in practice than insertion sort despite the same worst-case complexity.
- Simple to implement and explain
- Stable — equal elements keep relative order
- O(n) best case with early-exit optimization
- In-place with O(1) extra space
AI Mentor Explanation
A groundskeeper arranging trophies by height walks the shelf left to right, and any time a taller trophy sits directly left of a shorter one, swaps them on the spot before moving one step further. By the end of one full walk, the single tallest trophy has been pushed all the way to the far end of the shelf, guaranteed. Each subsequent walk covers one less trophy at the end since that position is now locked in place. If a full walk produces zero swaps, the groundskeeper knows the whole shelf is already ordered and stops immediately instead of walking it again unnecessarily.
Step-by-Step Explanation
Step 1
Sweep adjacent pairs
Walk from the start of the unsorted range to its end, comparing each adjacent pair.
Step 2
Swap out-of-order pairs
If the left element is greater than the right, swap them immediately and continue.
Step 3
Shrink the unsorted range
The largest element in the range is guaranteed to reach the end after one full sweep; shrink the boundary by one.
Step 4
Exit early if no swaps
Track whether any swap happened in a pass; if none did, the array is sorted and the algorithm stops.
What Interviewer Expects
- State O(n²) average/worst case and O(n) best case with the early-exit optimization
- Explain why exactly one element (the max of the remaining range) is guaranteed sorted per pass
- Confirm bubble sort is stable
- Acknowledge it is rarely used in production despite being easy to teach
Common Mistakes
- Forgetting the early-exit flag, missing the O(n) best case entirely
- Confusing bubble sort with selection sort (adjacent swaps vs single end-of-pass swap)
- Claiming bubble sort is unstable
- Overselling bubble sort’s real-world performance versus insertion sort
Best Answer (HR Friendly)
“Bubble sort repeatedly walks through the list, swapping any two neighboring items that are out of order, so the largest remaining item always ends up at the far end after each full pass. It is simple and stable, and with a small optimization it can detect an already-sorted list and stop early, but it is generally slower in practice than other simple sorts like insertion sort.”
Code Example
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 # already sorted, O(n) best case
return arr
print(bubble_sort([5, 1, 4, 2, 8])) # [1, 2, 4, 5, 8]Follow-up Questions
- How does the early-exit flag change bubble sort’s best-case complexity?
- Why is bubble sort stable, and why does that matter in practice?
- How does bubble sort compare to selection sort in number of swaps performed?
- Why is bubble sort rarely chosen for production systems despite its simplicity?
MCQ Practice
1. What is bubble sort’s best-case time complexity with the early-exit optimization?
If a full pass makes no swaps, the array is already sorted and the algorithm exits immediately, giving O(n) best case.
2. After the first full pass of bubble sort, what is guaranteed?
Each full pass bubbles the largest remaining element in the unsorted range all the way to the end.
3. Is bubble sort a stable sorting algorithm?
Bubble sort only swaps adjacent elements when the left one is strictly greater, so equal elements never cross each other.
Flash Cards
What happens on each pass of bubble sort? — Adjacent out-of-order pairs are swapped, bubbling the largest remaining element to the end.
What is bubble sort’s worst-case time complexity? — O(n²).
How can bubble sort achieve O(n) best case? — By tracking if any swap occurred in a pass and exiting early if not.
Is bubble sort stable? — Yes — it only swaps strictly out-of-order adjacent pairs.