Stability and comparison 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

Comparison sorting learns order through comparisons. Stability preserves relative order for equal keys. A comparison sort has an Ω(n log n) worst-case comparison lower bound when distinguishing all permutations of distinct items.

Work through an example

Records (score=2,A),(score=1,B),(score=2,C) become B,A,C in a stable score sort. A and C keep their original relative order.

Time and space complexity

Stable merge sort Θ(n log n) time/O(n) peak auxiliary storage; Python sorted is stable.

Why it works

Every merge chooses the left record first on equal keys, preserving earlier order.

Common mistakes

Stability is about equal keys, not identical records.
The comparison lower bound does not cover bounded-key counting sort.

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