Sorting & Searching

Here are the three quadratic sorts in real code. Each takes a list a, makes its own copy with a = a[:] so the caller's list is never changed, and returns a new sorted list. Watch the indentation: the lines indented under a for/while run once per pass of that loop.

1. bubble_sort: the outer for i is one full pass; the inner for j compares each neighbour pair a[j] and a[j+1] and swaps them if the left is bigger. The swapped flag is an optimisation: if a whole pass made no swaps the list is already sorted, so break exits early — that's the O(n) best case.
2. selection_sort: m = min(range(i, len(a)), key=lambda k: a[k]) finds the index of the smallest value from position i onward, then the swap a[i], a[m] = a[m], a[i] moves that minimum to the front of the unsorted part.
3. insertion_sort: key is the item we're placing. The while loop walks left, shifting bigger items one slot right (a[j+1] = a[j]), until it finds the gap where key belongs, then drops it in with a[j+1] = key.
4. The pattern a[j], a[j+1] = a[j+1], a[j] is Python's one-line swap — the two values trade places without a temporary variable.

What the output means: All three return the same sorted list, e.g. [5,2,8,1] → [1,2,5,8]. Bubble is the only one that can finish early (on already-sorted input); the other two always do the full O(n²) work.

Try this: Add a print(a) inside bubble_sort's outer loop and run it on [5,2,8,1] — you'll watch the largest value march to the right end one pass at a time.

Merge sort in code is two functions. merge_sort does the divide (split and recurse); the helper _merge does the combine (zip two already-sorted lists into one). Together they guarantee O(n log n) in every case.

1. Base case first: if len(a) <= 1: return a. A list of 0 or 1 items is already sorted, so recursion stops here — without a base case the function would call itself forever.
2. Divide: mid = len(a) // 2 splits in half. merge_sort(a[:mid]) sorts the left half and merge_sort(a[mid:]) the right — each call keeps halving until it hits the base case.
3. Combine in _merge: two pointers i and j walk the two sorted inputs. Each step appends the smaller front item and advances that pointer, so out comes out sorted in one linear pass.
4. The stability trick: using <= in if left[i] <= right[j] means when two items are equal, the one from the left half is taken first — so equal items keep their original order. That's what makes merge sort stable.
5. After one side empties, out.extend(left[i:]) / out.extend(right[j:]) tacks on whatever's left over (already sorted).

What the output means: merge_sort([5,2,8,1,9,3]) prints [1, 2, 3, 5, 8, 9].

Try this: Change <= to < in _merge. Sorting numbers you won't see a difference, but for equal keys the order flips — that single character is the whole difference between a stable and unstable sort.

Two versions of quicksort. The first is the readable one — it literally builds three lists — so you can see the idea. The second is the in-place version that real code uses: it rearranges the array using only swaps, so it needs no extra lists (O(1) extra space).

1. Readable version: pick pivot = a[len(a) // 2] (the middle element), then use three list comprehensions to build less, equal, and greater. The answer is quicksort(less) + equal + quicksort(greater) — sort the two outer groups and glue everything together with the equal block in the middle.
2. In-place version, the setup: lo and hi mark the slice being sorted. if hi is None: hi = len(a) - 1 fills in the end on the first call, and if lo >= hi: return is the base case (0 or 1 elements).
3. The Lomuto partition loop: the pivot is the last element a[hi]. A pointer i marks the boundary of the "smaller-than-pivot" zone. For each j, if a[j] < pivot we swap it into that zone and grow i. So all small values pile up on the left.
4. Placing the pivot: after the loop, one final swap a[i], a[hi] = a[hi], a[i] drops the pivot at index i — its final sorted position. Then we recurse on [lo, i-1] and [i+1, hi], the two sides around it.

What the output means: Both sort the same. The readable one returns a new list; the in-place one mutates a directly and returns nothing — you'd read the sorted result from a afterward.

Try this: Run the readable version on [3,3,3]: less and greater are empty, equal is all three, so it returns instantly. Handling duplicates cleanly is why the three-way (less/equal/greater) split is nice.

Heapsort in three lines by reusing Python's heapq. A heap is a structure that always lets you pull out the smallest item cheaply, so sorting becomes "pull the smallest, then the next smallest, …" until empty.

1. h = a[:] copies the list first so the original isn't disturbed.
2. heapq.heapify(h) rearranges h into a min-heap in O(n) — after this, h[0] is always the smallest element.
3. The list comprehension [heapq.heappop(h) for _ in range(len(h))] pops the smallest item repeatedly. Each pop is O(log n) and hands them back in increasing order — that's the sorted list.
4. The _ loop variable is a convention meaning "I don't care about this value, I just want to repeat len(h) times".

What the output means: heapsort([5,2,8,1]) prints [1, 2, 5, 8]. Total cost: O(n) to build plus n pops of O(log n) each = O(n log n).

Try this: This is the same tool RAG uses for top-k: a heap is the go-to when you want the smallest/largest items pulled off cheaply, one at a time.

Counting sort in code. Instead of comparing items, it builds a counts array where counts[v] tells you how many times value v appears, then rebuilds the sorted list from those tallies.

1. counts = [0] * (max_val + 1) makes one counter slot for every possible value from 0 up to max_val, all starting at zero.
2. First loop (count): for each x in the input, counts[x] += 1. One pass over the data — O(n).
3. Second loop (emit): enumerate(counts) gives each value and its count c. out.extend([value] * c) appends that value c times. Because we walk values 0, 1, 2, … in order, the output comes out sorted.
4. There is no if a < b anywhere — that's the whole point. Not comparing is how it sidesteps the O(n log n) wall.

What the output means: counting_sort([3,1,3,0,2], max_val=3) prints [0, 1, 2, 3, 3].

Try this: Try max_val=100 on the same tiny list. It still works but now allocates 101 slots for 5 numbers — a vivid demo of why counting sort only pays off when the value range is small.

This lab shows the everyday payoff of a stable sort: sorting by more than one key. Python's built-in sort (Timsort) is stable, meaning items with equal keys keep the order they were already in — and that lets you layer sorts.

1. results is a list of dictionaries, each with a doc, a score, and a source. We want them ordered by score (high first), and for equal scores, by source.
2. The layered trick: sort by the secondary key first (key=lambda r: r["source"]), then by the primary key (key=lambda r: r["score"], reverse=True). Because the sort is stable, the second sort preserves the source order among items with equal scores.
3. key=lambda r: ... tells sort what to compare for each item — here, reach into the dictionary and pull out a field. reverse=True flips to descending.
4. The one-call alternative: sorted(results, key=lambda r: (-r["score"], r["doc"])) uses a tuple as the key. Python compares tuples left-to-right, so this sorts by -score (negative = descending) and breaks ties by doc — both keys in a single sort.

What the output means: Both approaches order A and B (both score 0.9) ahead of C (0.7); the tuple key additionally guarantees A-before-B by document name.

Try this: Negating a number (-r["score"]) is the standard way to sort one field descending while others stay ascending inside a single tuple key — a trick worth memorising for interviews.

Three related tools for searching sorted data: a hand-written binary_search, the standard library's bisect, and a lower_bound variant. Binary search is famous for off-by-one bugs, so the boundary conventions here matter.

1. binary_search setup: lo, hi = 0, len(a) - 1. The comment "the range is inclusive [lo, hi]" means hi is a valid index, which is why the loop condition is while lo <= hi (with <=, not <).
2. The loop: mid = (lo + hi) // 2 is the middle index. If a[mid] equals the target we return mid. If it's too small we move lo = mid + 1 (search the right half); if too big, hi = mid - 1 (search the left half). Returning -1 means "not found".
3. bisect: bisect.bisect_left(a, 5) returns the index where 5 is (or where it would be inserted to stay sorted) — O(log n). bisect.insort(a, 6) inserts 6 in the correct spot, keeping a sorted. Use these instead of writing your own.
4. lower_bound uses a different convention: lo, hi = 0, len(a) is "half-open [lo, hi)" — hi is one past the end — so its loop is while lo < hi and it never does hi = mid - 1. It returns the leftmost index whose value is >= target, handy for finding insertion points and counting duplicates.

What the output means: binary_search([...], target) returns the index or -1; bisect_left(a, 5) returns 2; after insort(a, 6), a is [1,3,5,6,7,9].

Try this: Notice the two functions use different range conventions (inclusive [lo,hi] vs half-open [lo,hi)). Pick one convention and stick to it — mixing them is the #1 source of binary-search bugs.

Quickselect in code: find the k-th smallest value in O(n) average time by partitioning and recursing into just one side. The inner select(lo, hi) does the work on the slice between indices lo and hi.

1. a = a[:] copies so we don't disturb the caller. The nested function select can see a and k from the outer scope.
2. Random pivot: pivot = a[random.randint(lo, hi)] picks a random element. Randomising avoids the pathological O(n²) case that a fixed pivot hits on already-sorted input.
3. Three-way split: less, equal, and greater hold the values below, equal to, and above the pivot within the current slice a[lo:hi+1].
4. The three branches decide where k is: if k - lo < len(less) the target is in the smaller group, so recurse there; else if it falls inside the equal block we return pivot (found it); otherwise recurse into the greater group, shifting the start index past less and equal. Only one branch recurses — that's the speed-up.
5. Each branch first writes the reordered slice back with a[lo:hi+1] = less + equal + greater so indices line up before recursing.

What the output means: quickselect([7,2,9,1,5], 2) prints 5 — the 3rd smallest value (k=2 because k is counted from 0).

Try this: Change k to 0 (smallest) and 4 (largest) and confirm the answers. Finding the median is just quickselect with k = len(a)//2 — no full sort.

The classic interview question "find the k-th largest element" in one line, using a heap. The comment hints at the fuller technique interviewers like to hear about.

1. heapq.nlargest(k, nums) returns the k biggest values, already sorted largest-first. Indexing [-1] grabs the last of those — the smallest of the top k, which is exactly the k-th largest overall.
2. The comment "or maintain a size-k heap" points at the streaming version: keep a min-heap of size k, push each number, and pop the smallest whenever the heap grows past k. The root is then the k-th largest — this runs in O(n log k) and never stores more than k items, so it works on data too big to hold at once.

What the output means: For nums=[3,2,1,5,6,4], k=2 it returns 5 — the 2nd largest.

Try this: Say the trade-off out loud in an interview: nlargest is O(n log k) and simple; quickselect is O(n) average but trickier; full sorted() is O(n log n). Picking the right one for the constraints is what's being tested.

A favourite interview twist: binary-search a sorted array that has been rotated (e.g. [4,5,6,7,0,1,2]). The array isn't fully sorted, but at any midpoint one half still is — and that's enough to keep halving.

1. Standard binary-search skeleton: lo, hi, and mid = (lo + hi) // 2. If nums[mid] is the target, return it.
2. Which half is sorted? if nums[lo] <= nums[mid] the left half is in order; otherwise the right half is. Exactly one side is always cleanly sorted, even after rotation.
3. Is the target in the sorted half? When the left is sorted, check nums[lo] <= target < nums[mid] — if so, search left (hi = mid - 1), otherwise search right. The mirror logic applies when the right half is sorted.
4. Because each step still discards half the array, it stays O(log n) — the rotation costs nothing asymptotically.

What the output means: search([4,5,6,7,0,1,2], 0) returns 4 (the index of 0); a missing target returns -1.

Try this: The reusable idea: even when data isn't fully sorted, if you can identify a sorted region at each step you can still binary-search it. Spotting that invariant is the whole trick here.