Quick Sort

Intuition

Quick sort wins by turning one hard sorting problem into two smaller ones around a pivot. Pick a value, move every smaller value to its left, leave every greater-or-equal value to its right, and the pivot lands in its final sorted position. After that, the pivot never moves again. The same idea repeats on the left and right ranges.

How It Works

This lesson uses the Lomuto partition scheme: the pivot is always arr[hi], the last value of the current range. Pointer j scans from lo to hi - 1. Pointer i marks the next slot reserved for a value smaller than the pivot.

When arr[j] < pivot, the value belongs in the left partition. The algorithm swaps arr[j] with arr[i], then advances i. When arr[j] >= pivot, the value stays in the right partition and only j advances. After the scan finishes, the pivot swaps with arr[i]. That final swap puts the pivot exactly between the < pivot zone and the >= pivot zone.

The recursive calls then sort arr[lo..p-1] and arr[p+1..hi], where p is the pivot's final index. This version is in-place, but it is not stable: values equal to the pivot stay on the right side during partition, and swaps can change the relative order of duplicates.

Step By Step

The default input is [38, 12, 56, 7, 12, 41, 23]. The two 12 values are distinct: 12#1 starts at index 1 and 12#4 starts at index 4.

1. Start with range [0..6] and choose pivot 23 from index 6.
2. Scan j = 0: 38 >= 23, so 38 stays in the right zone and i remains 0.
3. Scan j = 1: 12#1 < 23, so swap it into slot 0. The left zone is now [12#1], and i advances to 1.
4. Scan j = 2: 56 >= 23, so it stays to the right.
5. Scan j = 3: 7 < 23, so swap it into slot 1. The left zone is now [12#1, 7], and i advances to 2.
6. Scan j = 4: 12#4 < 23, so swap it into slot 2. The left zone becomes [12#1, 7, 12#4].
7. Scan j = 5: 41 >= 23, so it stays to the right. Now swap pivot 23 into index 3. The array is [12#1, 7, 12#4, 23, 56, 41, 38], and index 3 is final.
8. Recurse left on [0..2]. Pivot 12#4 causes 7 to move left and then lands at index 2. Recurse again on [0..1], where pivot 7 lands at index 0.
9. Recurse right on [4..6]. Pivot 38 lands at index 4, then the remaining [56, 41] partitions around pivot 41, giving the final row [7, 12#1, 12#4, 23, 38, 41, 56].

In the animation, watch the pivot lane and the zone bands. The pivot lane tells you the fixed value for this partition; the bands under the row show which cells are already < pivot, which are scanned >= pivot, and which are still unknown.

Complexity

The worst case happens when partitions are badly unbalanced, such as repeatedly picking the smallest or largest value as pivot. This lesson intentionally uses the simple last-element pivot so the partition mechanics stay clear.

Edge Cases

• Empty arrays and single-element arrays are already sorted.
• Duplicate values are allowed, but this Lomuto version is not stable.
• Values equal to the pivot follow the >= pivot path and stay in the right zone during that partition.
• Already sorted input can be a worst-case pattern with a last-element pivot.
• Reverse sorted input also creates highly unbalanced partitions for this pivot rule.

Common Mistakes

• Using <= pivot in the partition guard while claiming the lesson is strict Lomuto; it changes where equal values go.
• Forgetting to swap the pivot with arr[i] after the scan, leaving the pivot at the end.
• Recursing on [lo..p] or [p..hi] instead of excluding the final pivot index.
• Treating quick sort as stable. The output values are sorted, but duplicate identities can move relative to one another.
• Moving i after every comparison. i advances only when a value is accepted into the < pivot zone.