Problem Description

You need to sort an array of integers in ascending order (from smallest to largest). The challenge is that you cannot use any built-in sorting functions and must achieve a time complexity of O(n log n) while using the smallest space complexity possible.

Given an input array like [5, 2, 3, 1], you should return [1, 2, 3, 5].

The solution implements a three-way partitioning quicksort algorithm. This approach works by:

1. Randomly selecting a pivot element x from the current range [l, r]
2. Partitioning the array into three sections:
   • Elements less than x (moved to the left)
   • Elements equal to x (kept in the middle)
   • Elements greater than x (moved to the right)
3. Using three pointers i, j, and k:
   • i tracks the boundary of elements less than x
   • j tracks the boundary of elements greater than x
   • k iterates through the unprocessed elements
4. Recursively sorting the left partition [l, i] and right partition [j, r]

The three-way partitioning is particularly efficient when the array contains duplicate values, as all elements equal to the pivot are placed in their final sorted position in a single pass. This avoids unnecessary recursive calls on elements that are already correctly positioned.

The random pivot selection helps avoid worst-case O(n²) performance that can occur with deterministic pivot selection on already sorted or reverse-sorted arrays, ensuring the expected O(n log n) time complexity.

Intuition

When we need to sort an array in O(n log n) time without built-in functions, we think about classic efficient sorting algorithms: merge sort, heap sort, or quicksort. Each has trade-offs in terms of space complexity and implementation complexity.

The key insight here is recognizing that quicksort, when implemented with in-place partitioning, achieves the best space complexity - O(log n) for the recursion stack in the average case. This makes it ideal for meeting the "smallest space complexity possible" requirement.

However, standard quicksort has a weakness: it can degrade to O(n²) time complexity in worst cases (like already sorted arrays). We address this by randomly selecting the pivot, which probabilistically ensures O(n log n) expected time complexity.

The solution takes this a step further by using three-way partitioning instead of the traditional two-way partition. Why? Consider an array with many duplicate values like [3, 1, 3, 4, 3, 2, 3]. With standard quicksort, if we pick 3 as the pivot, we'd split into "less than 3" and "greater than or equal to 3", meaning we'd have to recursively sort all those duplicate 3s again in the next iteration.

Three-way partitioning elegantly solves this by creating three regions: < pivot, = pivot, and > pivot. All elements equal to the pivot are placed in their final sorted position in one pass. This optimization is particularly powerful for arrays with many duplicates, reducing unnecessary recursive calls.

The implementation uses a clever single-pass approach with three pointers that simultaneously partition the array while maintaining the invariants that everything before i is less than the pivot, everything after j is greater than the pivot, and k tracks our current scanning position.

Learn more about Divide and Conquer, Sorting, Heap (Priority Queue) and Merge Sort patterns.

Solution Approach

The implementation uses a modified quicksort with three-way partitioning. Let's walk through how it works:

Main Structure: The solution defines a recursive helper function quick_sort(l, r) that sorts the subarray from index l to r inclusive. The base case checks if l >= r, meaning we have one element or an invalid range, so we return immediately.

Pivot Selection:

x = nums[randint(l, r)]

We randomly select a pivot element x from the current range. This randomization is crucial for avoiding worst-case performance on sorted or nearly-sorted inputs.

Three-Way Partitioning Setup:

i, j, k = l - 1, r + 1, l

• i = l - 1: Points to the last element less than the pivot (starts before the range)
• j = r + 1: Points to the first element greater than the pivot (starts after the range)
• k = l: Current element being examined

Partitioning Process: The main loop while k < j processes each unexamined element. For each nums[k], we have three cases:

1. Element less than pivot (nums[k] < x):

   nums[i + 1], nums[k] = nums[k], nums[i + 1]
   i, k = i + 1, k + 1

   • Swap with the element at i + 1 (first element in the "equal" region)
   • Increment both i and k to expand the "less than" region

2. Element greater than pivot (nums[k] > x):

   j -= 1
   nums[j], nums[k] = nums[k], nums[j]

   • Decrement j first to shrink the "unprocessed" region
   • Swap with the element at the new j position
   • Don't increment k since we need to examine the swapped element

3. Element equal to pivot:

   k = k + 1

   • Simply move to the next element, leaving it in place

Recursive Calls:

quick_sort(l, i)
quick_sort(j, r)

After partitioning, the array has three regions:

• [l, i]: Elements less than the pivot
• [i+1, j-1]: Elements equal to the pivot (already in correct position)
• [j, r]: Elements greater than the pivot

We recursively sort only the first and third regions, skipping the middle region entirely since equal elements are already correctly positioned.

Time and Space Complexity:

• Time: O(n log n) expected, O(n²) worst case (mitigated by random pivot)
• Space: O(log n) for recursion stack in average case, O(n) worst case

The three-way partitioning shines when there are duplicate elements, as it reduces the problem size more aggressively than standard two-way partitioning.

Example Walkthrough

Let's trace through the algorithm with the array [3, 1, 3, 2, 3, 4].

Initial Call: quick_sort(0, 5)

• Range: entire array [3, 1, 3, 2, 3, 4]
• Let's say random pivot selects nums[2] = 3
• Initialize: i = -1, j = 6, k = 0

Partitioning Process:

Step 1: k = 0, examining nums[0] = 3

• 3 == 3 (equal to pivot)
• Action: k = 1
• Array: [3, 1, 3, 2, 3, 4] (unchanged)
• Pointers: i = -1, j = 6, k = 1

Step 2: k = 1, examining nums[1] = 1

• 1 < 3 (less than pivot)
• Action: Swap nums[0] and nums[1], increment i and k
• Array: [1, 3, 3, 2, 3, 4]
• Pointers: i = 0, j = 6, k = 2

Step 3: k = 2, examining nums[2] = 3

• 3 == 3 (equal to pivot)
• Action: k = 3
• Array: [1, 3, 3, 2, 3, 4] (unchanged)
• Pointers: i = 0, j = 6, k = 3

Step 4: k = 3, examining nums[3] = 2

• 2 < 3 (less than pivot)
• Action: Swap nums[1] and nums[3], increment i and k
• Array: [1, 2, 3, 3, 3, 4]
• Pointers: i = 1, j = 6, k = 4

Step 5: k = 4, examining nums[4] = 3

• 3 == 3 (equal to pivot)
• Action: k = 5
• Array: [1, 2, 3, 3, 3, 4] (unchanged)
• Pointers: i = 1, j = 6, k = 5

Step 6: k = 5, examining nums[5] = 4

• 4 > 3 (greater than pivot)
• Action: Decrement j to 5, swap nums[5] with itself
• Array: [1, 2, 3, 3, 3, 4] (unchanged)
• Pointers: i = 1, j = 5, k = 5

Loop ends since k >= j

After partitioning:

• [1, 2] (indices 0-1): elements < 3
• [3, 3, 3] (indices 2-4): elements = 3 (already sorted!)
• [4] (index 5): elements > 3

Recursive Calls:

1. quick_sort(0, 1) to sort [1, 2]
   • Pivot: 2, partitions to [1] and [2]
   • Further recursive calls on single elements return immediately
2. quick_sort(5, 5) to sort [4]
   • Single element, returns immediately

Final Result: [1, 2, 3, 3, 3, 4]

Notice how all three 3s were placed in their final positions in a single partitioning pass - this is the power of three-way partitioning!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) on average, O(n²) in the worst case

The code implements a three-way partitioning quicksort algorithm.

• In the average case, the pivot divides the array into roughly equal parts at each recursion level, creating a recursion tree of depth log n. At each level, we perform O(n) work for partitioning, resulting in O(n log n) total time.
• In the worst case (despite random pivot selection), if we consistently get poor pivot choices that create highly unbalanced partitions, the recursion depth becomes O(n), leading to O(n²) time complexity.
• The three-way partitioning optimization helps when there are many duplicate elements by grouping equal elements together in one pass, potentially reducing the number of recursive calls.

Space Complexity: O(log n) on average, O(n) in the worst case

The space complexity comes from the recursive call stack:

• In the average case with balanced partitions, the maximum recursion depth is O(log n).
• In the worst case with unbalanced partitions, the recursion can go as deep as O(n).
• The algorithm sorts in-place without using additional arrays, so only the call stack contributes to space complexity.
• Each recursive call uses O(1) additional space for local variables (x, i, j, k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Pointer Management After Swapping

One of the most common mistakes in three-way partitioning is incorrectly managing the k pointer after swapping elements. Specifically, when swapping an element greater than the pivot:

Incorrect approach:

elif nums[k] > pivot:
    j -= 1
    nums[j], nums[k] = nums[k], nums[j]
    k += 1  # WRONG! Should not increment k

Why it's wrong: When we swap nums[k] with nums[j-1], the element that was at position j-1 is now at position k. We haven't examined this element yet, so we need to check it against the pivot. Incrementing k would skip this unexamined element.

Correct approach:

elif nums[k] > pivot:
    j -= 1
    nums[j], nums[k] = nums[k], nums[j]
    # Don't increment k - we need to examine the swapped element

2. Off-by-One Errors in Boundary Initialization

Another frequent mistake is incorrectly initializing the boundaries:

Incorrect initialization:

i, j, k = l, r, l  # WRONG! i should be l-1, j should be r+1

Why it's wrong:

• i should track the last element less than the pivot, so it starts at l-1 (before the range)
• j should track the first element greater than the pivot, so it starts at r+1 (after the range)

Correct initialization:

i, j, k = l - 1, r + 1, l

3. Forgetting to Handle Edge Cases

Missing base case:

def three_way_quick_sort(left, right):
    # Forgetting the base case leads to infinite recursion
    pivot = nums[randint(left, right)]  # This will fail when left > right
    # ... rest of the code

Correct approach:

def three_way_quick_sort(left, right):
    if left >= right:  # Essential base case
        return
    pivot = nums[randint(left, right)]
    # ... rest of the code

4. Using Fixed Pivot Selection

Poor pivot selection:

pivot = nums[left]  # Always choosing first element as pivot

Why it's problematic: This leads to O(n²) worst-case performance on already sorted or reverse-sorted arrays, which are common in real-world scenarios.

Better approach:

pivot = nums[randint(left, right)]  # Random pivot selection

5. Incorrect Recursive Calls

Wrong recursive boundaries:

# After partitioning with final i and j values
three_way_quick_sort(left, i - 1)  # WRONG! Should be (left, i)
three_way_quick_sort(j + 1, right)  # WRONG! Should be (j, right)

Why it's wrong: After the partitioning loop:

• Elements from left to i (inclusive) are less than the pivot
• Elements from j to right (inclusive) are greater than the pivot
• The boundaries should include these positions, not exclude them

Correct recursive calls:

three_way_quick_sort(left, i)
three_way_quick_sort(j, right)

Solution to Avoid These Pitfalls:

1. Test with small arrays to verify pointer movement: [2, 1, 2, 2, 3]
2. Trace through the algorithm step-by-step with paper and pencil
3. Add assertions during development to verify invariants:

   assert left <= i + 1 <= k <= j <= right + 1

4. Test edge cases: empty array, single element, all duplicates, already sorted
5. Visualize the three regions as you code: [< pivot | = pivot | unprocessed | > pivot]