Introduction

After quicksort partitions an array around a pivot, it has two sub-arrays to sort. For correctness, it does not matter which side you sort first, but for implementation quality it often does matter because the order affects recursion depth and stack usage.

Correctness: Either Side Can Go First

Quicksort works because partitioning places the pivot in its final sorted position and guarantees:

• every element on the left is less than or equal to the pivot
• every element on the right is greater than or equal to the pivot

Once that invariant holds, the left and right sub-arrays are independent. Sorting the left side first or the right side first leads to the same final result.

A simple recursive version in Python shows this clearly:

1def quicksort(arr, low, high):
2    if low >= high:
3        return
4
5    pivot_index = partition(arr, low, high)
6    quicksort(arr, low, pivot_index - 1)
7    quicksort(arr, pivot_index + 1, high)
8
9
10def partition(arr, low, high):
11    pivot = arr[high]
12    i = low
13
14    for j in range(low, high):
15        if arr[j] <= pivot:
16            arr[i], arr[j] = arr[j], arr[i]
17            i += 1
18
19    arr[i], arr[high] = arr[high], arr[i]
20    return i

If you swap the two recursive calls, the sorted output stays the same.

Why Smaller-First Is Better in Practice

The interesting part is stack depth. If you always recurse into both sides naively, worst-case quicksort can use deep recursion. A common optimization is:

• recurse into the smaller partition first
• handle the larger partition with iteration or tail-recursion elimination

That keeps the maximum stack depth to O(log n) even when partitions are unbalanced.

Example with Smaller-First Optimization

Here is a version that always recurses on the smaller side and loops on the larger side:

1def quicksort(arr, low, high):
2    while low < high:
3        pivot_index = partition(arr, low, high)
4
5        left_size = pivot_index - low
6        right_size = high - pivot_index
7
8        if left_size < right_size:
9            quicksort(arr, low, pivot_index - 1)
10            low = pivot_index + 1
11        else:
12            quicksort(arr, pivot_index + 1, high)
13            high = pivot_index - 1
14
15
16def partition(arr, low, high):
17    pivot = arr[high]
18    i = low
19
20    for j in range(low, high):
21        if arr[j] <= pivot:
22            arr[i], arr[j] = arr[j], arr[i]
23            i += 1
24
25    arr[i], arr[high] = arr[high], arr[i]
26    return i
27
28
29data = [9, 4, 7, 3, 10, 5, 1]
30quicksort(data, 0, len(data) - 1)
31print(data)

This still sorts correctly, but it is more careful about stack growth.

Why the Optimization Works

Suppose the array splits into sizes 2 and 1000. If you recurse into the large side first again and again, the call stack can grow badly. If you recurse into the side of size 2 first and then loop over the large side, the stack only needs to remember the small branches.

That is the main reason textbooks and production implementations often recommend smaller-first ordering. It does not improve the asymptotic time complexity of partitioning itself, but it improves space behavior.

Pivot Choice Still Matters More for Speed

Sorting the smaller partition first does not rescue a terrible pivot strategy. If you always pick the last element and the input is already sorted, you can still get O(n^2) comparisons.

Common pivot strategies include:

• random pivot
• median-of-three
• last element for simplicity

The partition-order optimization and good pivot selection solve different problems:

• pivot strategy helps runtime behavior
• smaller-first recursion helps stack usage

You often want both.

Iterative Quicksort and Explicit Stacks

If recursion depth is a concern, you can also write quicksort iteratively with your own stack:

1def iterative_quicksort(arr):
2    stack = [(0, len(arr) - 1)]
3
4    while stack:
5        low, high = stack.pop()
6        if low >= high:
7            continue
8
9        pivot_index = partition(arr, low, high)
10        left = (low, pivot_index - 1)
11        right = (pivot_index + 1, high)
12
13        if (left[1] - left[0]) > (right[1] - right[0]):
14            stack.append(left)
15            stack.append(right)
16        else:
17            stack.append(right)
18            stack.append(left)

Even here, many implementations push the larger segment first so the smaller segment is processed sooner, again helping keep the stack smaller.

Common Pitfalls

• Believing one side must be sorted first for correctness is incorrect; either side works.
• Ignoring recursion depth can cause stack overflows on large or adversarial inputs.
• Confusing pivot choice with sub-array order mixes two separate optimization decisions.
• Assuming textbook recursive quicksort is good enough for all production inputs can be risky.
• Forgetting the base case for empty or single-element sub-arrays causes infinite recursion.

Summary

• Left-first and right-first quicksort are both correct.
• The better practical choice is usually to sort the smaller partition first.
• Smaller-first ordering reduces recursion depth and improves space usage.
• Good pivot selection still matters for time complexity.
• Production-quality quicksort often combines careful pivoting with smaller-first recursion or an iterative fallback.