Insertion and selection sort

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

Insertion sort maintains a sorted prefix and inserts the next value by shifting larger ones. Selection sort repeatedly finds the smallest remaining value and swaps it into place.

Work through an example

On [3,1,2], insertion moves 3 right for 1, then inserts 2 before 3. Selection first swaps 1 into position zero; ordinary swaps can disrupt equal-key order.

Time and space complexity

Both worst-case Θ(n²)/O(1) auxiliary; insertion best Θ(n) on already sorted data.

Why it works

Insertion's prefix is sorted; selection's prefix contains the smallest finalized values.

Common mistakes

Basic selection sort is not stable.
Do not stop insertion shifting before placing the saved value.

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