Counting and radix sorting

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

Counting sort uses a bounded integer key range; radix sort processes digits with a stable per-digit sort. They bypass comparison lower bounds by exploiting representation constraints.

Work through an example

Keys [2,0,2,1] give counts [1,1,2] and sorted output [0,1,2,2]. LSD radix must preserve prior low-digit ordering when sorting the next digit.

Time and space complexity

Counting O(n+K) time/O(K) counts; radix O(d(n+B)) for d digits and base B, plus output storage.

Why it works

Counting tracks exact multiplicities; stable digit passes progressively order the processed digits.

Common mistakes

Huge sparse key ranges waste memory.
Negative keys require an offset or explicit policy.

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