The hard requirement is that the list must be sorted.
Binary search throws away half the list based on a single comparison, and that discard is only valid when the data is ordered. On unsorted input the middle value says nothing about which side holds the target.
That one requirement is why sorting matters so much. It unlocks binary search, two pointers, prefix sums, and a dozen other patterns in this course, so sorting is often the setup step rather than the goal.
The cost matters too. Sorting is O(n log n), so it pays for itself across many searches but not for a single lookup, which is the calculation from lesson 2-1.
This unit is about how sorting itself works.
Bubble sort: the teaching sort
Bubble sort is the simplest sorting algorithm to understand, and understanding it teaches you how to reason about sorts in general.
The idea is to sweep left to right comparing each adjacent pair, swapping any pair that is out of order. One full sweep is a pass.
After the first pass the largest value has bubbled all the way to the end, which is a guarantee worth stating precisely: nothing larger can remain to its left, because any larger value would have been carried along by the sweep.
That guarantee is what lets the next pass stop one cell earlier, and repeating until a pass makes zero swaps means the list is sorted.
Nobody ships bubble sort, since it is O(n²), but interviewers still ask for an explanation of it, and its pass-by-pass trace is the clearest picture of what sorting actually does.
Pass by pass
Each printed line is the list after one complete pass.
def bubble_sort(nums): nums = nums[:] n = len(nums) for end in range(n - 1, 0, -1): swapped = False for i in range(end): if nums[i] > nums[i + 1]: nums[i], nums[i + 1] = nums[i + 1], nums[i] swapped = True print("after pass:", nums) if not swapped: break return nums print(bubble_sort([5, 3, 8, 1, 2]))
Output
after pass: [3, 5, 1, 2, 8] after pass: [3, 1, 2, 5, 8] after pass: [1, 2, 3, 5, 8] after pass: [1, 2, 3, 5, 8] [1, 2, 3, 5, 8]
nums = nums[:] copies the input, so the caller's list is left alone. That is a courtesy Python's own sorted extends and list.sort does not.
The outer loop counts end down from n−1, which is the shrinking boundary. Each pass ends one cell earlier because the previous pass locked a value into place at the back.
Tracing the values shows the guarantee holding. After pass 1 the 8 is at the end, after pass 2 the 5 is in place behind it, and after pass 3 the list is fully ordered.
The fourth pass is the early exit doing its job. It swapped nothing, swapped stayed False, and the break fired, which is what makes bubble sort O(n) on an already-sorted list.
Selection sort: the other O(n²) classic
Selection sort reaches the same result with a different move. Rather than swapping neighbors, it selects the right value for each position directly.
Find the smallest value in the whole list and swap it into position 0. Find the smallest of what remains and swap it into position 1. Repeat until every position is filled.
Two facts about it are worth knowing before writing it.
It always does about n²/2 comparisons, even on an already-sorted list, because finding the smallest of the rest requires scanning the rest every single time. Bubble sort's zero-swap early exit beats it outright on nearly-sorted data.
It never does more than n swaps, at most one per position. That mattered historically when a swap was expensive, such as moving a large record across a slow disk, while bubble sort can make O(n²) swaps on the same data.
Interviewers pair these two sorts because comparing them forces the real question: what does each pass actually guarantee? A bubble pass guarantees the largest remaining value reaches the end, and a selection pass guarantees the front of the list is finished and will never be touched again.
selection_sort
For each position from the left, find the smallest remaining value and swap it in.
def selection_sort(nums): nums = nums[:] for i in range(len(nums)): smallest = i for j in range(i + 1, len(nums)): if nums[j] < nums[smallest]: smallest = j nums[i], nums[smallest] = nums[smallest], nums[i] return nums print(selection_sort([64, 25, 12, 22, 11])) print(selection_sort([3, 1, 2]))
Output
[11, 12, 22, 25, 64] [1, 2, 3]
The inner loop only looks for the minimum's index, tracking it in smallest and touching nothing. The single swap happens after that loop ends, which is what caps the algorithm at n swaps.
Starting smallest = i rather than at some sentinel value means the current position is its own first candidate. If nothing beats it, the swap is a harmless no-op with itself.
The inner range begins at i + 1, so the already-finished prefix is never rescanned. That shrinking remainder is why the comparison count is about n²/2 rather than n².
Both calls sort correctly, and the second is worth noting for the swap count. Sorting [3, 1, 2] needs two swaps, while bubble sort would also reach the answer but by moving neighbors repeatedly.
About n²/2 comparisons, exactly as on any other input.
Every position still scans the rest of the list for the minimum, because selection sort has no way to detect sortedness. Finding the minimum of the remainder requires examining the remainder, whether or not a swap follows.
What changes on sorted input is only the swap count, since every minimum is already where it belongs and each swap is a no-op. The comparisons, which are the dominant cost, are unaffected.
Bubble sort with the zero-swap early exit finishes a sorted list in one O(n) pass, which is a concrete reminder worth carrying forward. Two algorithms with the same worst-case Big-O can behave very differently on friendly inputs.
That is also why real libraries care about nearly-sorted data. Python's sort detects existing runs and exploits them, which is a refinement neither of these two classics attempts.
Because doubling the input size quadruples the work, so a million items means about a trillion comparisons.
n² grows brutally, and the arithmetic from lesson 1-1 already showed it. Pair-checking 1,000 items cost about 500,000 steps, and at n = 1,000,000 the count is 10¹².
A trillion comparisons is not a slow program, it is a program that does not finish. At even a hundred million comparisons per second that is roughly three hours for one sort.
The sorts in the next two lessons bring this down to O(n log n), which is about 20 million steps for a million items. That is a fifty-thousandfold reduction, and it is the difference between an unusable algorithm and the one in every standard library.
The reason those sorts win is a structural change rather than a tuning one. Bubble and selection both compare a value against many others, while merge and quicksort split the problem so that each comparison does more work.