Quicksort: partition, duplicates and stack
Contract and prerequisite
Use the existing sorting and asymptotic-bounds foundations. This lesson uses Lomuto partition on inclusive range A[lo..hi], pivot A[hi], comparison <=. Other partition schemes have different returned indices and traces; never mix them.
1. Derive the partition
Set p=A[hi], i=lo−1. For j=lo,...,hi−1: if A[j]<=p, increment i and swap A[i],A[j]. Finally swap A[i+1],A[hi] and return q=i+1. Before each iteration, A[lo..i]<=p, A[i+1..j−1]>p, A[j..hi−1] is unclassified and A[hi]=p. Empty ranges are permitted. A successful comparison enlarges the small region; failure enlarges the large region. The final swap places the pivot between them.
Quicksort: if lo>=hi return; q=partition(lo,hi); sort(lo,q−1); sort(q+1,hi). The pivot is excluded from both recursive calls. This gives termination even when q is an endpoint. Partition only places the pivot correctly; the two sides are not necessarily sorted.
Worked trace on [4,2,4,1,3]: p=3. j=0 fails, j=1 succeeds giving [2,4,4,1,3], j=2 fails, j=3 succeeds giving [2,1,4,4,3]. Final swap gives [2,1,3,4,4], q=2. The left side [2,1] still needs sorting. There were four pivot comparisons.
2. Balanced and unbalanced work
Partition of n elements costs Θ(n). Balanced subproblems give 2T(n/2)+Θ(n)=Θ(n log n). Endpoint pivots give T(n−1)+Θ(n)=Θ(n²), since (n−1)+(n−2)+...+1 comparisons sum to n(n−1)/2. Sorted ascending distinct input with last-element pivot is such a worst case. Random pivot choice gives expected Θ(n log n) on distinct keys, but does not remove the quadratic worst case.
With this <= convention, all-equal input puts q=hi every time. Therefore it remains quadratic even if the pivot record is selected randomly: randomization cannot distinguish equal keys. Three-way partition groups <p, =p, >p and recurses only on the strict groups. An all-equal array then needs one linear scan. Three-way partition is a different algorithm, not a changed trace for Lomuto.
3. Space, stability and implementation safeguards
Partition uses O(1) auxiliary storage, but recursive quicksort has Θ(log n) stack depth on balanced splits and Θ(n) in the worst case. Thus calling it in-place must state whether the recursion stack is excluded. To guarantee O(log n) stack, recursively process only the smaller side and loop on the larger side: each nested recursive call at least halves the active size. This changes stack usage, not the quadratic time of poor pivots.
Standard swapping quicksort is unstable: [2a,2b,1] becomes [1,2b,2a] at the first partition, reversing the two equal records. Choosing <= alone does not guarantee stability as it did for merge's tie rule. In actual C, use a signed index type when representing lo−1; an unsigned index wraps at lo=0. Guard the base case before using A[hi]. Our pseudocode assumes valid bounds and values fitting their numeric type.
Checkpoints
Always write the partition convention before tracing. Separate expected time from worst-case guarantees and partition memory from full recursive memory. Duplicate behavior is not covered by a distinct-key randomized analysis.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. The stated partition of [4,2,4,1,3] returns q:
A. 0 B. 1 C. 2 D. 4
Answer: C
A: Pivot 3 has two smaller records.
B: Index 1 precedes the final pivot.
C: Final array is [2,1,3,4,4].
D: 3 is not the maximum.
P02. Correct recursive ranges after this partition?
A. [lo,q] and [q,hi] B. [lo,q−1] and [q+1,hi] C. Only [lo,q] D. Whole range again
Answer: B
A: Including q can prevent progress.
B: Pivot is final and excluded.
C: Both unsorted sides must be handled.
D: Size would not decrease.
P03. All-equal input under <= Lomuto has time:
A. Θ(1) B. Θ(n) C. Θ(n log n) D. Θ(n²)
Answer: D
A: All records must be inspected.
B: The equal group is not removed together.
C: Splits are not balanced.
D: Every pivot is at hi, leaving n−1 records.
P04. How can stack be bounded by O(log n) despite bad pivots?
A. Always recurse left first B. Recurse smaller side; loop larger C. Use last pivot always D. Remove base case
Answer: B
A: The left side may be the large side.
B: Nested recursive sizes at least halve.
C: Last pivot does not limit depth.
D: Termination would fail.
P05. Sorted 5 distinct elements, last pivot: total pivot comparisons?
A. 4 B. 8 C. 10 D. 25
Answer: C
A: Only the first partition.
B: Sum is 4+3+2+1.
C: 4+3+2+1=10.
D: n² is an asymptotic scale, not this exact count.
P06. Which claim about ordinary swapping quicksort is correct?
A. Always stable B. Random pivot eliminates worst case C. Partition needs Θ(n) buffer D. Can reverse equal records
Answer: D
A: [2a,2b,1] is a counterexample.
B: Randomization changes expectation, not all outcomes.
C: This partition uses constant extra storage.
D: [2a,2b,1] becomes [1,2b,2a].
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in