Randomized Quicksort — Why Random Pivots Make Sorting Fast

Why Randomized Quicksort Matters

Quicksort is one of the most widely used sorting algorithms in practice. It is the default sorting algorithm in C (qsort), Java (Arrays.sort for primitives), and many other languages. However, standard Quicksort with a fixed pivot (like first or last element) has O(n²) worst-case behavior on already-sorted arrays. Randomized Quicksort fixes this by choosing a random pivot, making the worst case exponentially unlikely.

Why this matters for your career:

Quicksort is the default sorting algorithm in most standard libraries — understanding it is essential
Randomized pivot selection is a classic example of how randomness improves algorithm performance
Quicksort is a frequent interview topic (implement it, analyze it, improve it)
The analysis introduces the powerful concept of expected runtime vs. worst-case runtime

What Is Randomized Quicksort?

Randomized Quicksort is exactly like standard Quicksort — divide and conquer, pick a pivot, partition, recurse — except the pivot is chosen uniformly at random from the array. This simple change eliminates the pathological worst-case behavior.

Algorithm Pseudocode

function randomized_quicksort(arr, low, high):
    if low < high:
        pivot_index = randomized_partition(arr, low, high)
        randomized_quicksort(arr, low, pivot_index - 1)
        randomized_quicksort(arr, pivot_index + 1, high)

function randomized_partition(arr, low, high):
    random_index = random(low, high)
    swap(arr[random_index], arr[high])
    return partition(arr, low, high)  // standard Lomuto or Hoare partition

Implementation

import random

def randomized_quicksort(arr):
    """Sort arr in-place using randomized Quicksort."""
    def _quicksort(low, high):
        if low < high:
            pivot_idx = _randomized_partition(low, high)
            _quicksort(low, pivot_idx - 1)
            _quicksort(pivot_idx + 1, high)

    def _randomized_partition(low, high):
        # Choose random pivot and swap to end
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]

        # Standard partition (Lomuto)
        pivot = arr[high]
        i = low - 1

        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]

        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    _quicksort(0, len(arr) - 1)
    return arr

Example Usage

arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = randomized_quicksort(arr)
print(f"Sorted: {sorted_arr}")
# Output: Sorted: [3, 9, 10, 27, 38, 43, 82]

# Test on already-sorted array (worst case for standard Quicksort)
already_sorted = list(range(1000))
result = randomized_quicksort(already_sorted.copy())
print(f"Already sorted: first 5 = {result[:5]}, last 5 = {result[-5:]}")
# Output: Already sorted: first 5 = [0, 1, 2, 3, 4], last 5 = [995, 996, 997, 998, 999]

Why Randomization Helps

With a fixed pivot (first or last element), Quicksort hits O(n²) when the array is already sorted or reverse-sorted. These are common real-world inputs!

| Input | Standard Quicksort | Randomized Quicksort | |-------|-------------------|---------------------| | Random data | O(n log n) | O(n log n) | | Already sorted | O(n²) ❌ | O(n log n) ✅ | | Reverse sorted | O(n²) ❌ | O(n log n) ✅ | | All same values | O(n²) ❌ (without 3-way partition) | O(n log n) ✅ | | Adversarial input | O(n²) ❌ | O(n log n) ✅ |

A determined adversary cannot construct an input that forces O(n²) behavior because the pivot choice is random.

Expected Time Complexity Analysis

Let T(n) be the expected runtime. When we choose a random pivot, each of the n positions is equally likely. The recurrence is:

T(n) = O(n) + sum_{k=0}^{n-1} P(pivot is k-th smallest) * (T(k) + T(n-k-1))

Since the pivot is equally likely to be any rank:

T(n) = O(n) + (1/n) * sum_{k=0}^{n-1} (T(k) + T(n-k-1))

Solving this recurrence gives:

T(n) = O(n log n)

Intuitive Explanation

On average, a random pivot splits the array into two parts of roughly equal size (within a 3:1 ratio). The depth of recursion is O(log n), and each level does O(n) work. Hence O(n log n) expected time.

Space Complexity

| Version | Space | Notes | |---------|-------|-------| | In-place (Lomuto) | O(log n) | Stack space for recursion | | In-place (Hoare) | O(log n) | More efficient partitioning | | Naive (new arrays) | O(n) | Each recursion creates new lists |

Randomized Quicksort is an in-place algorithm — it sorts the original array without significant extra memory.

Comparison with Other Sorting Algorithms

| Algorithm | Average | Worst Case | Space | Stable | |-----------|---------|------------|-------|--------| | Randomized Quicksort | O(n log n) | O(n log n) expected | O(log n) | No | | Mergesort | O(n log n) | O(n log n) | O(n) | Yes | | Heapsort | O(n log n) | O(n log n) | O(1) | No | | Introsort | O(n log n) | O(n log n) | O(log n) | No | | Timsort | O(n log n) | O(n log n) | O(n) | Yes |

Introsort (used in C++ std::sort) starts with Quicksort and switches to Heapsort if recursion depth exceeds O(log n), guaranteeing worst-case O(n log n).

Three-Way Partitioning (Dutch National Flag)

When there are many duplicate values, standard partitioning wastes time. Three-way partitioning splits into three groups: < pivot, == pivot, > pivot.

def randomized_quicksort_3way(arr):
    def _quicksort(low, high):
        if low < high:
            lt, gt = _randomized_partition_3way(low, high)
            _quicksort(low, lt - 1)
            _quicksort(gt + 1, high)

    def _randomized_partition_3way(low, high):
        rand_idx = random.randint(low, high)
        pivot = arr[rand_idx]

        lt = low    # boundary for < pivot
        gt = high   # boundary for > pivot
        i = low

        while i <= gt:
            if arr[i] < pivot:
                arr[lt], arr[i] = arr[i], arr[lt]
                lt += 1
                i += 1
            elif arr[i] > pivot:
                arr[gt], arr[i] = arr[i], arr[gt]
                gt -= 1
            else:
                i += 1

        return lt, gt

    _quicksort(0, len(arr) - 1)
    return arr

This variant handles arrays with many duplicates efficiently.

Summary

Randomized Quicksort is a textbook example of how a small dose of randomness can dramatically improve an algorithm. By choosing pivots randomly, we eliminate the pathological O(n²) worst case of standard Quicksort and achieve O(n log n) expected time for all inputs.

Key takeaways:

Random pivot selection eliminates worst-case O(n²) for already-sorted inputs
Expected runtime is O(n log n) — matching the average case of standard Quicksort
No adversary can force worst-case behavior (pivot is random)
In-place sorting with O(log n) stack space
Default sorting algorithm in most standard libraries
Three-way partitioning handles duplicate values efficiently

What's Next: Monte Carlo vs. Las Vegas Algorithms

The next chapter distinguishes two types of randomized algorithms: Monte Carlo (may give wrong answer, but fast) and Las Vegas (always correct, runtime may vary).

Practical Performance Tuning

| Optimization | Benefit | |-------------|--------| | Random pivot | Avoids O(n²) on sorted data | | Switch to insertion sort for small subarrays (n < 16) | Reduces recursion overhead ~15% faster | | Three-way partition | Handles duplicates efficiently | | Tail recursion elimination | Reduces stack depth | | Introsort fallback | Guarantees worst-case O(n log n) | | Median-of-three for small arrays | Reduces random calls, improves cache |

These optimizations make the difference between textbook code and production-ready sorting.