Sorting & Searching

1 · Why sorting matters (and the O(n log n) wall) basic

Here's a puzzle that feels like cheating the first time you see it. You have a million numbers and someone asks "is 847,203 in here?" Unsorted, you have no choice but to look at every single one — a million checks in the worst case. But sort the list once, and suddenly the same question takes about twenty checks, forever after. You didn't get a faster computer; you paid a one-time cost to impose order, and order is what lets you skip. That trade — spend once to sort, then reap cheap lookups again and again — is why sorting is the quiet workhorse under so much software.

Think of a physical dictionary versus a shoebox of loose word-cards. Both hold the same words, but the dictionary is sorted, so you find "penguin" by flipping to roughly the middle, then the middle of what's left — never reading front to back. The shoebox forces you to paw through every card. Sorting is the act of turning the shoebox into the dictionary. And because it's so foundational, it's also the most-studied problem in all of computer science: decades of clever people have squeezed it, which is exactly why it's the perfect capstone — it ties together divide-and-conquer, heaps, recursion, and the cost model from every earlier part of this track.

The common beginner mistake is to treat "sort it" as free or magical — to reach for sorted() reflexively without a feel for what it costs. It is not free: it has a price, and remarkably, there's a hard floor on that price that no amount of cleverness can break through for the general case. That floor has a name — the O(n log n) wall — and understanding why it exists is what separates someone who memorises sort names from someone who knows when a linear-time trick is even possible. So before we write a single sort, let's name the wall.

Sorting unlocks other algorithms: binary search needs sorted data, deduplication and median-finding get easy, and many two-pointer tricks (D1) require order. Comparison sorts — those that only compare pairs of elements — cannot beat O(n log n) in the worst case. That's a proven lower bound: there are n! possible orderings and each comparison gives one bit, so you need at least log₂(n!) ≈ n log n comparisons. Only sorts that don't compare (counting/radix) escape it, under special conditions.

2 · The O(n²) sorts — learn them, then never use them basic

Think about how you'd sort a hand of playing cards. Most people do it without being taught: you pick up cards one at a time and slide each new one into its right spot among the cards you're already holding. That instinct is a sorting algorithm — insertion sort — and it works beautifully for thirteen cards. The trouble starts when the "hand" is thirteen million records, because the very thing that makes it feel natural — comparing the new item against the ones you've already placed — means the work piles up as a loop inside a loop. That's the O(n²) shape from D1, and it's the reason these three sorts are a rite of passage you learn and then retire.

Why bother learning sorts you're told never to ship? Two reasons. First, they're the clearest possible illustration of the O(n²) trap — nested loops, work growing with every pair of elements — so they cement the cost intuition you'll apply to your own code for the rest of your career. Second, one of them (insertion sort) is genuinely useful in a niche the fast sorts can't beat: tiny or nearly-sorted arrays, which is why production sorts quietly fall back to it. Bubble and selection, by contrast, earn their keep purely as teaching tools; you will essentially never choose them on purpose in real code.

The three differ only in how they move elements toward order — bubble swaps neighbours until the big ones float to the end, selection repeatedly hunts down the smallest and places it, insertion grows a sorted region one card at a time — but they share the same fatal ceiling: all three re-scan the data again and again, so ten times more input means roughly a hundred times more work. The common mistake is assuming "it ran fine on my test data" tells you anything; a hidden O(n²) sort sails through a 100-item test and then melts on a 100,000-item production load. The diagram lines up all three strategies so you can see they reach the same destination by different (equally slow) roads.

pythondef bubble_sort(a):            # repeatedly swap adjacent out-of-order pairs
    a = a[:]                        # copy — don't mutate caller's list
    for i in range(len(a)):
        swapped = False
        for j in range(len(a) - 1 - i):   # biggest "bubbles" to the end
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]; swapped = True
        if not swapped: break       # already sorted -> O(n) best case
    return a

def selection_sort(a):         # pick the smallest, put it first, repeat
    a = a[:]
    for i in range(len(a)):
        m = min(range(i, len(a)), key=lambda k: a[k])
        a[i], a[m] = a[m], a[i]
    return a

def insertion_sort(a):         # grow a sorted prefix, inserting each item
    a = a[:]
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]; j -= 1
        a[j+1] = key
    return a

3 · Merge sort — divide & conquer advanced

Imagine you and three friends have to alphabetise a giant stack of exam papers. The clumsy way: one person tries to sort the whole pile alone. The smart way: split the pile into four, each person sorts their quarter, and then you combine the four sorted quarters into one. Merging already-sorted piles is startlingly easy — you just keep taking whichever pile's top paper comes first alphabetically. That "split the work, solve the pieces, cleverly combine" instinct is divide-and-conquer, and merge sort is its purest expression. It's also the moment this track levels up: we finally break the O(n²) ceiling.

The key realisation — and it surprises people — is that merging two already-sorted lists is cheap, only O(n). Because each list is sorted, you never search: you just compare the two front items, take the smaller, and advance. So the plan writes itself: keep splitting the array in half until each piece is a single element (a one-item list is trivially sorted — there's nothing to arrange), then merge pairs back up. Halving gives about log n levels, and each level's merges together touch all n items once, so the total is n × log n — guaranteed, in the best and worst case, because the split doesn't care what the data looks like.

Merge sort buys you two things quadratic sorts can't: a rock-solid O(n log n) with no bad-luck worst case, and stability (equal items keep their original order, thanks to one <= in the merge). The price — and there's always a price — is O(n) extra memory for the scratch space the merge needs. The common mistake is forgetting that cost and merge-sorting data that barely fits in RAM, doubling your footprint; when memory is tight you'd reach for an in-place sort like quicksort or heapsort instead. Read the diagram as a tree: grey arrows going down are the split, blue arrows coming back up are the merge.

Merge sort splits the array in half, sorts each half recursively, then merges the two sorted halves in linear time. Guaranteed O(n log n) in all cases and stable — but needs O(n) extra space for the merge.

pythondef merge_sort(a):
    if len(a) <= 1:
        return a                    # base case
    mid = len(a) // 2
    left = merge_sort(a[:mid])      # divide + conquer each half
    right = merge_sort(a[mid:])
    return _merge(left, right)      # combine

def _merge(left, right):           # merge two sorted lists — O(n)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # <= keeps it STABLE (ties keep order)
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])   # leftovers
    return out

print(merge_sort([5, 2, 8, 1, 9, 3]))    # [1,2,3,5,8,9]

4 · Quicksort — partition in place advanced

Picture a room full of people you need to line up by height, but you're not allowed a second empty room to sort them in. Merge sort needed that spare room (its O(n) scratch space); quicksort refuses it. Instead you grab one person — call them the pivot — and bark a single instruction: "everyone shorter, go to my left; everyone taller, go to my right." Now the pivot is standing in their exact final position, and you've got two smaller groups to sort by the same rule. You never left the room. That in-place shuffle is quicksort, and it's the sort your language's standard library most likely uses under the hood for raw speed.

The clever bit is that one partition pass does something merge sort's split doesn't: it places the pivot permanently. After partitioning, the pivot never moves again — everything smaller is already left of it, everything larger right of it — so quicksort needs no separate merge step at the end. Recurse on the left group and the right group and the whole array falls into order for free. When the pivot lands near the middle each time, you get about log n levels of halving over n-work partitions: the familiar O(n log n) average, but with tiny constants and cache-friendly memory access, which is why it's usually the fastest in practice.

Here's the catch, and it's the thing interviewers love to probe. Quicksort's speed depends entirely on picking a balanced pivot. Choose badly — say, always grab the last element — and hand it an already-sorted array, and every partition splits off just one element instead of half. Now you have n levels instead of log n, and the whole thing collapses to O(n²) — slower than merge sort exactly when you'd least expect it. The common mistake is shipping a fixed-pivot quicksort and getting bitten by real data that happens to arrive pre-sorted; the fix is a single line — pick the pivot at random — which makes the bad case astronomically unlikely. The diagram shows one partition step; watch the pivot snap into its final home.

Quicksort picks a pivot, partitions the array into "less than pivot" and "greater than pivot," and recurses on each side. Average O(n log n), in-place (O(log n) stack), and usually the fastest in practice — but a bad pivot on already-sorted data gives O(n²) worst case (fixed by randomizing the pivot).

python# Clear (not in-place) — great for understanding
def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    less = [x for x in a if x < pivot]
    equal = [x for x in a if x == pivot]
    greater = [x for x in a if x > pivot]
    return quicksort(less) + equal + quicksort(greater)

# In-place Lomuto partition — how it's really done (O(1) extra space)
def quicksort_inplace(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return
    pivot = a[hi]; i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]; i += 1
    a[i], a[hi] = a[hi], a[i]           # pivot to its final place
    quicksort_inplace(a, lo, i - 1)
    quicksort_inplace(a, i + 1, hi)

5 · Heapsort advanced

Suppose you're organising a talent show and you have a magic box: drop any number of contestants in, and it always hands you back the single best one on demand. Sorting everyone becomes trivial — ask the box for the best, write them down, ask again, write down the next-best, and repeat until the box is empty. What comes out is a perfectly ranked list. That magic box is a heap (you built one from scratch in D4), and using it this way to sort is heapsort. It's the sort that gives you the strong guarantees of merge sort without merge sort's extra memory.

Mechanically it's two phases. First, heapify the array — rearrange it in place so it obeys the heap's "each parent beats its children" rule; surprisingly, this costs only O(n), not O(n log n). Then repeatedly pull the minimum off the top, each pop costing O(log n) to re-settle the heap. Do that n times and you've spent n log n total — and crucially, the whole dance happens inside the original array, so extra memory is O(1). That combination — guaranteed O(n log n) worst case and constant extra space — is heapsort's unique selling point; neither quicksort (bad worst case) nor merge sort (extra space) offers both.

So why isn't heapsort the default everywhere? Because raw wall-clock speed usually loses to quicksort. The reason is cache behaviour: heapsort hops around the array to parent and child indices that are far apart in memory, defeating the CPU's habit of pre-loading nearby data, whereas quicksort scans in tidy neighbouring runs. It's also not stable — equal items can get reordered. The common mistake is picking heapsort for general sorting because its Big-O looks best on paper; in practice you'd reach for it specifically when you need the worst-case guarantee and can't spare memory (embedded systems, real-time deadlines). For everyday work, the heap's real home is top-k: keep only the best few from a huge stream, which is exactly the RAG pattern you'll see in the used-in-the-course notes.

Heapsort uses the heap from D4: build a heap (O(n)), then repeatedly pop the min/max (O(log n) each) into the output. Guaranteed O(n log n) and O(1) extra space — but not stable and typically slower than quicksort due to poor cache behaviour.

pythonimport heapq

def heapsort(a):
    h = a[:]
    heapq.heapify(h)                    # O(n) — turn list into a min-heap in place
    return [heapq.heappop(h) for _ in range(len(h))]   # pop in sorted order

print(heapsort([5, 2, 8, 1]))     # [1, 2, 5, 8]

6 · Beating the wall — counting & radix sort expert expert

We keep calling O(n log n) a "wall" — so how do the pros sometimes sort in flat linear time? The trick is a loophole hiding in the fine print of that lower bound. The proof says any sort that works by comparing pairs of elements can't beat O(n log n). The escape, then, is obvious once you see it: don't compare. If you never ask "is A bigger than B?", the proof simply doesn't apply to you, and the wall isn't your wall.

Here's the everyday version of the idea. Imagine sorting a stack of exam papers by score, where every score is 0 to 100. Instead of comparing papers to each other, you set out 101 labelled trays and drop each paper into the tray matching its score. When you're done, just gather the trays in order — the papers come out sorted, and you never once compared two papers. That's counting sort: one pass to tally how many of each value you have (O(n)), one pass over the possible values to emit them in order (O(n + k), where k is the size of the value range). Radix sort extends the same tally-don't-compare idea to bigger numbers or strings by sorting one digit at a time, from least significant to most, giving O(d·(n+k)) for d digits.

But loopholes have conditions, and here's the one that bites. Counting sort needs one tray per possible value, so its cost and memory scale with k, the value range — not just n, the number of items. Sorting five numbers that could each be up to a billion would demand a billion trays: technically linear in k, catastrophically wasteful in reality. The common mistake is being seduced by "linear time!" and reaching for counting sort on wide-ranging data (arbitrary floats, huge IDs, timestamps), where it's dramatically worse than a plain comparison sort. These sorts win only when the range is small and known: ages, test scores, single bytes, fixed-length keys. Everywhere else, the comparison sorts you just learned remain the right default. The diagram walks through a tiny counting sort on values in 0..3.

These don't compare elements, so they sidestep the O(n log n) bound — at the cost of only working on specific data. Counting sort sorts integers in a known small range in O(n + k) by tallying counts. Radix sort applies counting sort digit-by-digit for larger integers/strings, O(d·(n+k)).

pythondef counting_sort(a, max_val):        # a: non-negative ints in [0, max_val]
    counts = [0] * (max_val + 1)
    for x in a:
        counts[x] += 1                   # tally each value — O(n)
    out = []
    for value, c in enumerate(counts):
        out.extend([value] * c)          # emit in order — O(n + k)
    return out

print(counting_sort([3, 1, 3, 0, 2], max_val=3))   # [0,1,2,3,3]

7 · Stability & Python's Timsort intermediate

Here's a bug that has burned every data engineer at least once. You have a table of orders already sorted by date. You sort it again by customer name to group each customer's orders together — and to your horror, within each customer the dates are now scrambled. You didn't touch the dates; the sort silently reshuffled equal-name rows. That single frustrating experience is why the property called stability exists, and why it's one of the most quietly important guarantees a sort can make.

A sort is stable if, when two items compare equal on the sort key, it keeps them in the order they already had. Picture sorting a deck of cards first by number, then by suit: a stable sort leaves the numbers in order within each suit; an unstable one might jumble them. Why does anyone care? Because stability is what makes multi-key sorting work by layering. Want results ordered by score, and ties broken by source? Sort by the secondary key (source) first, then by the primary key (score) — a stable sort preserves the source order inside each group of equal scores, so two simple sorts compose into one compound ordering. Without stability that trick is impossible and you'd need a single, fiddlier comparison.

Python hands you all of this for free: sorted() and list.sort() use Timsort, a hybrid invented by Tim Peters for CPython that merges the best of two worlds — merge sort's guaranteed O(n log n) worst case and stability, plus insertion sort's speed on small chunks. Its real superpower is being adaptive: it detects already-sorted stretches (called "runs") in your data and skips work, so nearly-sorted input runs in close to O(n). The common mistake is assuming every language's sort is stable and porting the "sort twice" idiom to one whose default sort isn't (C's qsort, for instance) — where it quietly breaks. In Python you can rely on it; the lab shows the layered-sort payoff.

A sort is stable if equal elements keep their original relative order. This matters when you sort by multiple keys in stages. Python's sorted() / list.sort() use Timsort — a hybrid of merge sort and insertion sort that's stable, adaptive (O(n) on nearly-sorted data by exploiting existing "runs"), and worst-case O(n log n).

pythonresults = [
    {"doc": "A", "score": 0.9, "source": "kb"},
    {"doc": "B", "score": 0.9, "source": "web"},
    {"doc": "C", "score": 0.7, "source": "kb"},
]
# Because Timsort is STABLE, sort by the secondary key first, then primary:
results.sort(key=lambda r: r["source"])          # secondary
results.sort(key=lambda r: r["score"], reverse=True)  # primary — ties keep source order

# key= computes a sort key once per item (the "decorate-sort-undecorate" idiom)
top = sorted(results, key=lambda r: (-r["score"], r["doc"]))   # tuple = multi-key

8 · Binary search — the payoff of sorted data advanced

Remember the "guess my number between 1 and 100" game? The winning strategy isn't to guess 1, 2, 3… — it's to guess 50, learn "higher" or "lower," then guess 75 or 25, halving what's left every time. You corner any number in at most seven guesses. Binary search is exactly that game played on a sorted array, and it's the reward you collect for all the sorting effort in this chapter: because the data is in order, one look at the middle tells you which half to throw away.

The power is hard to overstate until you see the numbers. Every comparison discards half the remaining candidates, so the cost is O(log n) — and logarithms grow at a crawl. A thousand items take about ten checks; a million take about twenty; a billion take about thirty. Doubling your data adds a single extra step. That's the difference between an O(n) scan that grinds through everything and an O(log n) search that barely notices the size. But it only works on sorted data — order is the whole reason you can trust that the target must be on one particular side. On an unsorted list you have no such clue and you're back to looking at everything.

There's a reason binary search is a rite of passage: it is famously, notoriously bug-prone. It's a handful of lines, yet getting the boundaries right defeats even strong programmers — a landmark study found most published implementations were subtly broken for years. The traps are all off-by-one: is the range inclusive [lo, hi] or half-open [lo, hi)? Should the loop be while lo <= hi or while lo < hi? Do you move to mid + 1 or mid? The common mistake is mixing conventions mid-function — pairing an inclusive range with a half-open update — which produces a search that works on most inputs and infinite-loops or misses on a few. The cure is discipline: pick one convention, apply it consistently, and lean on the standard library's bisect whenever you can. The diagram traces a search for 11 so you can watch half the array vanish each step.

On a sorted array, binary search finds an element in O(log n) by repeatedly halving the search range. Getting the boundaries right is famously bug-prone; here's the canonical correct form, plus Python's batteries-included bisect.

pythondef binary_search(a, target):        # a must be sorted ascending
    lo, hi = 0, len(a) - 1
    while lo <= hi:                  # <= : the range is inclusive [lo, hi]
        mid = (lo + hi) // 2         # no overflow in Python
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1            # search the right half
        else:
            hi = mid - 1            # search the left half
    return -1                       # not found

# The standard library — O(log n) search & sorted insertion point
import bisect
a = [1, 3, 5, 7, 9]
bisect.bisect_left(a, 5)        # 2 — index of 5 (or where it'd go)
bisect.insort(a, 6)             # keeps a sorted: [1,3,5,6,7,9]

# Variant: leftmost index whose value >= target (a "lower bound")
def lower_bound(a, target):
    lo, hi = 0, len(a)          # half-open [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target: lo = mid + 1
        else: hi = mid
    return lo

9 · Quickselect — the k-th element in O(n) expert expert

Someone hands you a million exam scores and asks for the median. The obvious move is to sort them all and grab the middle one — O(n log n), done. But pause: sorting arranges every element relative to every other, and you only wanted one value. That's like alphabetising an entire library just to find the book that would sit exactly in the middle of the shelf. You did a mountain of work you're about to throw away. There's a way to get that single answer in O(n) — linear time — and it recycles machinery you already own.

Quickselect is quicksort with a lazy streak. It partitions around a pivot just like quicksort — after which the pivot sits in its final sorted position, smaller values left, larger right. Now comes the insight: you know the pivot's exact rank (its index). If that rank equals the k you're hunting, you're done — the pivot is the answer. If k is smaller, it must be in the left group, so recurse there; if larger, recurse right. Either way you throw one whole side away and never look at it again. Quicksort recurses into both halves (that's where its extra log n factor comes from); quickselect recurses into one.

That single change is the whole speed-up. When each pivot roughly halves the range, the work is n + n/2 + n/4 + …, which sums to about 2n — linear on average, versus the O(n log n) of a full sort. It shares quicksort's Achilles' heel — a pathological pivot gives an O(n²) worst case, cured the same way, with a random pivot. Knowing quickselect matters because "find the k-th thing" is everywhere: medians, percentiles, and top-k selection. The common mistake is reflexively sorting to answer these; but note the flip side — if you need several order statistics or the data is already sorted for other reasons, a full sort can be the better call. The trade-offs box after the lab lays out when to pick quickselect, a heap, or a plain sort. The diagram shows one partition where k lands right on the pivot.

To find the k-th smallest (or the median, or top-k), you don't need a full sort. Quickselect reuses quicksort's partition but only recurses into the side that contains k — giving O(n) average time instead of O(n log n).

pythonimport random

def quickselect(a, k):               # k-th smallest, 0-indexed
    a = a[:]
    def select(lo, hi):
        pivot = a[random.randint(lo, hi)]   # random pivot avoids worst case
        # three-way partition around the pivot value
        less = [x for x in a[lo:hi+1] if x < pivot]
        equal = [x for x in a[lo:hi+1] if x == pivot]
        greater = [x for x in a[lo:hi+1] if x > pivot]
        if k - lo < len(less):
            a[lo:hi+1] = less + equal + greater
            return select(lo, lo + len(less) - 1)
        elif k - lo < len(less) + len(equal):
            return pivot                    # k lands in the pivot block
        else:
            a[lo:hi+1] = less + equal + greater
            return select(lo + len(less) + len(equal), hi)
    return select(0, len(a) - 1)

nums = [7, 2, 9, 1, 5]
print(quickselect(nums, 2))          # 5 — the 3rd smallest (0-indexed k=2)

Exercises expert

🎯 Interview practice interview

The interview questions this topic gets asked — worked, with code. For the full pattern catalog see D8 · Big Tech DSA patterns.

pythonimport heapq
def find_kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]   # or maintain a size-k heap

pythondef search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target: return mid
        if nums[lo] <= nums[mid]:            # left half sorted
            if nums[lo] <= target < nums[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                                 # right half sorted
            if nums[mid] < target <= nums[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

Checkpoint — you've completed the DSA track when you can… expert

people = [("ada", 30), ("bob", 25), ("cy", 30), ("dot", 25)]
by_age = sorted(people, key=lambda p: p[1])   # O(n log n), stable
print(by_age)
# [('bob',25), ('dot',25), ('ada',30), ('cy',30)]
# bob before dot, ada before cy -> original order preserved within equal ages

def merge_sort(a):                     # O(n log n) time, O(n) space
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= keeps it stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

print(merge_sort([5, 2, 9, 1, 5, 6]))   # [1, 2, 5, 5, 6, 9]

def quicksort(a, lo=0, hi=None):       # avg O(n log n), worst O(n^2)
    if hi is None: hi = len(a) - 1
    if lo >= hi: return a
    pivot = a[hi]; i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]; i += 1
    a[i], a[hi] = a[hi], a[i]          # pivot to its final place
    quicksort(a, lo, i - 1)
    quicksort(a, i + 1, hi)
    return a

print(quicksort([3, 6, 1, 8, 2, 9, 4]))   # [1, 2, 3, 4, 6, 8, 9]

def bisect_left(a, x):                 # first index where a[i] >= x
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x: lo = mid + 1
        else:          hi = mid
    return lo

def search_range(a, x):                # O(log n)
    lo = bisect_left(a, x)
    if lo == len(a) or a[lo] != x:
        return [-1, -1]
    hi = bisect_left(a, x + 1) - 1     # first index > x, minus one
    return [lo, hi]

print(search_range([5, 7, 7, 8, 8, 8, 10], 8))   # [3, 5]
print(search_range([5, 7, 7, 8, 8, 8, 10], 6))   # [-1, -1]

import random

def quickselect(a, k):                 # k is 1-based; avg O(n)
    a = a[:]                           # copy so we don't mutate caller's list
    lo, hi = 0, len(a) - 1
    target = k - 1
    while lo < hi:
        p = random.randint(lo, hi)     # random pivot avoids worst case
        a[p], a[hi] = a[hi], a[p]
        pivot = a[hi]; i = lo
        for j in range(lo, hi):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]; i += 1
        a[i], a[hi] = a[hi], a[i]
        if i == target: return a[i]
        if i < target:   lo = i + 1    # recurse into one side only
        else:            hi = i - 1
    return a[lo]

print(quickselect([7, 2, 9, 1, 5, 3], 3))   # 3  (3rd smallest)

import heapq

def merge_k_sorted(lists):             # O(N log K)
    heap = []
    for li, lst in enumerate(lists):   # seed with each list's head
        if lst:
            heapq.heappush(heap, (lst[0], li, 0))
    out = []
    while heap:
        val, li, idx = heapq.heappop(heap)
        out.append(val)
        if idx + 1 < len(lists[li]):   # push the next item from that list
            heapq.heappush(heap, (lists[li][idx + 1], li, idx + 1))
    return out

print(merge_k_sorted([[1, 4, 7], [2, 5, 8], [3, 6, 9]]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Knowledge check check yourself