Quickselect and selection tradeoffs

What is sorting?

Sorting puts values in an order, usually smallest to largest. Different sorting algorithms move and compare values in different ways, so their time and memory costs differ. Selection is a related task: finding a particular ranked value, such as the third smallest, without necessarily sorting everything.

Example: Sorting [8, 2, 5] gives [2, 5, 8]. The second smallest value is 5. If records have equal sort keys, a stable sort keeps their original relative order.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Recursion

Understand the idea

Selection finds a rank without fully sorting. Quickselect follows only the partition containing the rank. Heaps fit streaming top-K; sorting is useful when all ordered results are needed.

Work through an example

The lab's copied three-way selection handles duplicates but is deliberately not an in-place implementation. For [5,1,5,2,9], rank 2 is 5.

Time and space complexity

Randomized quickselect expected O(n), worst O(n²); this copied version can use O(n²) peak space in bad recursion, unlike in-place selection.

Why it works

Discarded regions cannot contain the desired rank; adjust k when entering the higher region.

Common mistakes

Rank zero is smallest; kth-largest requires conversion.
Deterministic middle-position pivot has no random expected guarantee.

Chapter lab · Python implementation

Sorting makes order-dependent reasoning possible but adds preprocessing cost. The lab implements stable merge sort and a simple partition-based selection baseline. Compare them with in-place quickselect, counting/radix methods, and small-input insertion sort. Stability means preserving the original order of records with equal sort keys.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def merge_sort(values):
    if len(values)<2:
        return values.copy()
    middle=len(values)//2
    left=merge_sort(values[:middle])
    right=merge_sort(values[middle:])
    merged=[]
    i=j=0
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            merged.append(left[i]); i+=1
        else:
            merged.append(right[j]); j+=1
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged

def select(values,k):
    if not 0<=k<len(values):
        raise ValueError('invalid rank')
    pivot=values[len(values)//2]
    lower=[x for x in values if x<pivot]
    equal=[x for x in values if x==pivot]
    higher=[x for x in values if x>pivot]
    if k<len(lower):
        return select(lower,k)
    if k<len(lower)+len(equal):
        return pivot
    return select(higher,k-len(lower)-len(equal))

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert merge_sort([3,1,2,1])==[1,1,2,3]
assert merge_sort([])==[]
assert all(select([5,1,5,2,9],k)==sorted([5,1,5,2,9])[k] for k in range(5))

CHECK YOUR UNDERSTANDING