023. Three-Way Sort 0/1/2

Foundation · Download this solution · All solutions and shared helpers

Problem

Sort a mutable list containing only 0, 1 and 2 in one pass, using constant auxiliary space. Return the same list. Empty input is valid. Values outside these three categories are outside the contract.

Examples

Example 1

sort_three([2, 0, 2, 1, 1, 0])
=> [0, 0, 1, 1, 2, 2]

Unknown replacements are inspected again.

Example 2

sort_three([])
=> []

The unknown region is initially empty.

Example 3

sort_three([2, 2, 0])
=> [0, 2, 2]

Repeated twos expose the no-advance branch.

Reveal the worked solution and reasoning

Why this mechanism works

Maintain a classified prefix of zeros, a following region of ones, an unknown middle and a suffix of twos. Sending a two to the right brings an unknown value back, so inspect that replacement before advancing. Sending a zero left brings back a known one, or swaps the current cell with itself.

State and boundaries

[0,low) is zero; [low,current) is one; [current,high) is unknown; [high,n) is two. high is exclusive.

Protocol

Set low=current=0 and high=n.
While unknown cells remain inspect nums[current].
For zero swap with low and advance both.
For one advance current.
For two shrink high, swap, and keep current fixed.

Visualization

[ zeros | ones | unknown | twos ]
0      low   current   high    n
                2 -> right; inspect replacement

Python implementation

def sort_three(nums):
    low = current = 0
    high = len(nums)
    while current < high:
        if nums[current] == 0:
            nums[low], nums[current] = nums[current], nums[low]
            low += 1
            current += 1
        elif nums[current] == 1:
            current += 1
        else:
            high -= 1
            nums[current], nums[high] = nums[high], nums[current]
    return nums

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

sort_three([2, 0, 2, 1, 1, 0])

L2 sort_three: low = current = 0
nums=[2, 0, 2, 1, 1, 0]; low=0; current=0

L3 sort_three: high = len(nums)
nums=[2, 0, 2, 1, 1, 0]; low=0; current=0; high=6

L12 sort_three: high -= 1
nums=[2, 0, 2, 1, 1, 0]; low=0; current=0; high=5

L13 sort_three: nums[current], nums[high] = nums[high], nums[current]
nums=[0, 0, 2, 1, 1, 2]; low=0; current=0; high=5

L7 sort_three: low += 1
nums=[0, 0, 2, 1, 1, 2]; low=1; current=0; high=5

L8 sort_three: current += 1
nums=[0, 0, 2, 1, 1, 2]; low=1; current=1; high=5

L7 sort_three: low += 1
nums=[0, 0, 2, 1, 1, 2]; low=2; current=1; high=5

L8 sort_three: current += 1
nums=[0, 0, 2, 1, 1, 2]; low=2; current=2; high=5

L12 sort_three: high -= 1
nums=[0, 0, 2, 1, 1, 2]; low=2; current=2; high=4

L13 sort_three: nums[current], nums[high] = nums[high], nums[current]
nums=[0, 0, 1, 1, 2, 2]; low=2; current=2; high=4

L10 sort_three: current += 1
nums=[0, 0, 1, 1, 2, 2]; low=2; current=3; high=4

L10 sort_three: current += 1
nums=[0, 0, 1, 1, 2, 2]; low=2; current=4; high=4

Result: [0, 0, 1, 1, 2, 2]. Unknown replacements are inspected again.

sort_three([])

L2 sort_three: low = current = 0
nums=[]; low=0; current=0

L3 sort_three: high = len(nums)
nums=[]; low=0; current=0; high=0

Result: []. The unknown region is initially empty.

Why the solution is correct

Each branch extends a correctly classified region while preserving the others. The unknown interval loses one cell per iteration, proving termination. When it is empty, the three classified regions form the required sorted order.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Advancing current after swapping a two can skip another two or a zero. Mixing inclusive and exclusive high conventions corrupts the region boundaries.

Reasoning card

State: [0,low) is zero; [low,current) is one; [current,high) is unknown; [high,n) is two. high is exclusive.

Invariant: Left is all 0, middle processed region all 1, right all 2.

Decision to rehearse: Maintain three classified regions; one branch must not advance current.

Finish: For two shrink high, swap, and keep current fixed

Transfer exercise

Partition arbitrary values relative to a pivot into smaller, equal and larger regions.