I find randomized algorithms genuinely counterintuitive the first time I encounter them, because they introduce something that feels almost paradoxical: deliberately injecting randomness into a computation to make it more reliable, not less. My favorite way to frame this is through Randomized QuickSort, which I use as my central example in this article — by randomly choosing a pivot instead of always picking, say, the last element, I can take an algorithm with a fragile worst case and turn it into one whose bad behavior becomes vanishingly unlikely on any input, adversarial or not.
History and Background
The formal study of randomized algorithms as a distinct area of computer science developed substantially through the 1970s, with foundational contributions from researchers including Michael Rabin, whose 1976 work on randomized primality testing was one of the field’s landmark early results, and Robert Solovay and Volker Strassen, who independently developed a related randomized primality test around the same time.
Randomized QuickSort itself, which is my focus for the implementation in this article, is a natural extension of Tony Hoare’s original 1959–1961 QuickSort algorithm (which I cover in depth in my dedicated QuickSort article). The randomized variant — choosing a uniformly random pivot at each partitioning step — became a standard technique for taming QuickSort’s worst-case behavior, and it’s discussed extensively in Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms, which is where I first studied the formal expected-running-time analysis I present later in this article.
Problem Statement
The general problem randomized algorithms address is this: for many computational problems, a deterministic algorithm’s performance can depend heavily on the specific input it receives, and in the worst case, that performance can be poor — sometimes exploitably so, if an adversary can construct inputs designed to trigger the worst case. Randomized algorithms address this by making some of the algorithm’s internal decisions depend on random choices rather than purely on the input, so that no fixed input can reliably trigger bad performance across repeated runs.
Specifically, for Randomized QuickSort, I want to sort an array of $n$ elements while ensuring that no particular input (including adversarially chosen ones) can force the $O(n^2)$ worst-case behavior with high probability.
Core Concepts
- Deterministic algorithm: An algorithm whose behavior (including running time) is entirely determined by its input — running it twice on the same input always produces the same sequence of operations.
- Randomized algorithm: An algorithm that makes some decisions based on random values, so that its behavior (though not its final correctness, in most cases) can vary across different runs on the same input.
- Las Vegas algorithm: A randomized algorithm that always produces a correct result, but whose running time is a random variable — Randomized QuickSort is a Las Vegas algorithm, since it always correctly sorts, but its running time depends on the random pivot choices made.
- Monte Carlo algorithm: A randomized algorithm that runs in a fixed (or bounded) amount of time but may produce an incorrect result with some small probability — a different category from Las Vegas algorithms, though I mention it here for contrast since both terms come up frequently in this area.
- Expected running time: The average running time of a randomized algorithm, computed as an expectation over the algorithm’s internal random choices — not an average over different inputs, but over the randomness the algorithm itself introduces.
How It Works
For Randomized QuickSort specifically, here’s the process I follow, which differs from standard QuickSort in exactly one step:
- If the subarray has fewer than 2 elements, it’s already sorted (base case).
- Choose a pivot uniformly at random from the current subarray, rather than always using a fixed position like the last element.
- Swap the randomly chosen pivot into the last position of the subarray (so the existing Lomuto partition logic can proceed unchanged).
- Partition the subarray around this pivot, exactly as in standard QuickSort.
- Recursively apply Randomized QuickSort to the subarray before the pivot.
- Recursively apply Randomized QuickSort to the subarray after the pivot.
Working Principle
The internal logic behind why this works relies on a subtle but important shift in perspective: instead of asking “what is the worst-case running time for this specific input?”, I ask “what is the expected running time, averaged over my own random choices, for any input?”
Because the pivot is chosen randomly and independently at each partitioning step, no input — no matter how carefully constructed — can force a bad partition every time. An adversary who doesn’t know (or can’t predict) my random choices cannot reliably construct an array that triggers the $O(n^2)$ behavior; the worst case can still theoretically occur (if I happen to get unlucky with every single random choice), but the probability of that happening becomes vanishingly small as $n$ grows, and the expected running time across all possible sequences of random choices remains $O(n \log n)$.
Mathematical Foundation
I derive the expected running time of Randomized QuickSort using indicator random variables, which I also introduce in more general depth in my dedicated article on that topic.
Let $X$ be the total number of comparisons Randomized QuickSort performs while sorting $n$ distinct elements $z_1 < z_2 < \dots < z_n$ (using $z_i$ to denote the $i$-th smallest element in sorted order). I define an indicator random variable for each pair:
$$ X_{ij} = \begin{cases} 1 & \text{if } z_i \text{ and } z_j \text{ are ever compared} \ 0 & \text{otherwise} \end{cases} $$
so that the total comparisons can be written as:
$$ X = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} X_{ij} $$
The key probabilistic claim is: $z_i$ and $z_j$ are compared if and only if, among the elements $z_i, z_{i+1}, \dots, z_j$, either $z_i$ or $z_j$ is the first one chosen as a pivot (since choosing anything strictly between them as pivot first would separate them into different partitions before they’re ever compared). Since the pivot at each relevant step is chosen uniformly at random among the elements still under consideration, and there are $j – i + 1$ elements in this range, the probability that $z_i$ or $z_j$ is chosen first among them is:
$$ P(X_{ij} = 1) = \frac{2}{j – i + 1} $$
By linearity of expectation:
$$ E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} $$
Substituting $k = j – i$ and bounding the resulting sum using the harmonic series $H_n = \sum_{k=1}^{n} \frac{1}{k} \approx \ln n$, this evaluates to:
$$ E[X] = O(n \log n) $$
This confirms that regardless of the input array’s arrangement — sorted, reverse-sorted, or arbitrary — Randomized QuickSort’s expected number of comparisons (and hence its expected running time) is $O(n \log n)$.
Diagrams
Here’s the high-level flow showing where randomness enters the algorithm:
flowchart TD
A[Unsorted Subarray] --> B{Length less than 2?}
B -- Yes --> C[Already Sorted, Return]
B -- No --> D["Choose pivot index uniformly at random"]
D --> E["Swap random pivot into last position"]
E --> F["Partition around pivot (Lomuto scheme)"]
F --> G[Recursively sort left partition]
F --> H[Recursively sort right partition]
G --> I[Combined Array is Sorted]
H --> IAnd here’s a diagram contrasting deterministic vs. randomized pivot selection risk:
flowchart LR
A["Deterministic pivot (e.g., last element)"] --> B["Adversary can construct worst-case input"]
B --> C["O(n^2) guaranteed on that specific input"]
D["Randomized pivot"] --> E["No input can reliably trigger worst case"]
E --> F["O(n log n) expected, regardless of input"]Pseudocode
RANDOMIZED-QUICKSORT(A, low, high)
if low < high
pivotIndex = RANDOMIZED-PARTITION(A, low, high)
RANDOMIZED-QUICKSORT(A, low, pivotIndex - 1)
RANDOMIZED-QUICKSORT(A, pivotIndex + 1, high)
RANDOMIZED-PARTITION(A, low, high)
randomIndex = RANDOM-INTEGER(low, high) // uniform over [low, high]
swap A[randomIndex] and A[high]
return PARTITION(A, low, high) // standard Lomuto partition
PARTITION(A, low, high)
pivot = A[high]
i = low - 1
for j = low to high - 1
if A[j] <= pivot
i = i + 1
swap A[i] and A[j]
swap A[i + 1] and A[high]
return i + 1
Step-by-Step Example
Since the specific execution path of a randomized algorithm depends on the actual random values drawn, I traced my tested C implementation using a fixed random seed (srand(42)) so the result is fully reproducible. I ran it on:
$$ [33, 10, 55, 71, 29, 3, 18] $$
Rather than trace every random pivot choice by hand (which would depend on the specific pseudo-random number generator’s internal sequence), I want to focus on what matters conceptually: at each recursive call, a pivot index is drawn uniformly at random from the current subarray’s range, that element is swapped to the end, and then the exact same Lomuto partitioning logic I describe in my QuickSort article proceeds from there. Regardless of which specific pivots were drawn, the algorithm is guaranteed to terminate with a correctly sorted array, since correctness doesn’t depend on which pivots are chosen — only the performance does.
Running my tested implementation with seed 42 produced the fully sorted output:
$$ [3, 10, 18, 29, 33, 55, 71] $$
which I verified directly by compiling and executing the program.
Time Complexity
- Best Case: $O(n \log n)$ — occurs when random pivot choices happen to produce well-balanced partitions.
- Average/Expected Case: $O(n \log n)$ — this is the headline result, proven rigorously via the indicator random variable argument above, and it holds for every input, not just “typical” ones.
- Worst Case: $O(n^2)$ — still theoretically possible (for example, if the random number generator happened to choose the smallest or largest remaining element as pivot at every single step), but the probability of this occurring shrinks extremely rapidly as $n$ grows, making it a non-issue in practice.
Space Complexity
Randomized QuickSort has the same space profile as standard QuickSort:
- Auxiliary space for data: $O(1)$, since it sorts in-place.
- Recursive call stack: $O(\log n)$ expected, since partitions are expected to be reasonably balanced; $O(n)$ in the (very unlikely) worst case.
Correctness Analysis
I want to draw a clear distinction here: the correctness of Randomized QuickSort (that it always produces a sorted array) does not depend on randomness at all — it follows exactly the same partitioning correctness argument I use in my QuickSort article, since randomization only affects which element is chosen as pivot, not the logic of partitioning or recursion itself.
What randomization affects is performance, not correctness. This is precisely what makes Randomized QuickSort a Las Vegas algorithm: it is always correct, and only its running time is a random variable. I find this an important distinction to hold onto, since it’s easy to conflate “randomized” with “probably correct” — for Las Vegas algorithms like this one, correctness is guaranteed; only speed is probabilistic.
Advantages
- Removes the dependency on input arrangement for triggering worst-case behavior — no adversarial input can reliably force $O(n^2)$ performance.
- Simple to implement: it requires only a small modification (random pivot selection) to an existing QuickSort implementation.
- Provides strong average-case guarantees ($O(n \log n)$ expected) without needing assumptions about the input distribution, since the randomness comes from the algorithm itself, not the data.
- Broadly applicable technique — randomization for robustness against adversarial inputs is used well beyond sorting, in areas like hashing (randomized hash functions to avoid adversarial collision attacks) and computational geometry.
Disadvantages
- Still has a theoretical (if extremely unlikely) worst case of $O(n^2)$, which may be unacceptable in hard real-time systems requiring absolute guarantees.
- Requires a source of randomness, which introduces its own considerations — a poor-quality random number generator could undermine the theoretical guarantees.
- Running time varies between executions on the same input, which can make performance debugging and benchmarking slightly less straightforward than with a fully deterministic algorithm.
- Not inherently stable, inheriting this limitation from standard QuickSort.
Applications
- General-purpose sorting where robustness against adversarial or pathological input matters, such as any system processing untrusted or externally supplied data.
- Randomized selection algorithms (Quickselect), used to find the $k$-th smallest element in expected linear time.
- Skip lists, a randomized alternative to balanced binary search trees, offering expected $O(\log n)$ operations through randomized structure rather than strict balancing rules.
- Randomized primality testing (Miller-Rabin), a Monte Carlo algorithm that determines primality with high probability far faster than deterministic methods for large numbers.
- Load balancing and hashing schemes that use randomization to avoid worst-case collision patterns from adversarial or unusually structured input data.
Implementation in C
Here is my tested implementation of Randomized QuickSort:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Swaps two integers via pointers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Chooses a uniformly random pivot index, swaps it into the last
// position, then performs the standard Lomuto partition
int randomPartition(int arr[], int low, int high) {
int randomIndex = low + rand() % (high - low + 1);
swap(&arr[randomIndex], &arr[high]);
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
void randomizedQuickSort(int arr[], int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
randomizedQuickSort(arr, low, pi - 1);
randomizedQuickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
srand(42); // fixed seed for reproducibility in this demonstration
int arr[] = {33, 10, 55, 71, 29, 3, 18};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
printArray(arr, n);
randomizedQuickSort(arr, 0, n - 1);
printf("After sorting: ");
printArray(arr, n);
return 0;
}
Sample Input and Output
Input:
33 10 55 71 29 3 18
Output (verified by compiling and running the code above, with a fixed seed of 42 for reproducibility):
Before sorting: 33 10 55 71 29 3 18
After sorting: 3 10 18 29 33 55 71
Optimization Techniques
- Use a high-quality random number generator. For serious applications (beyond demonstration code using
rand()), a better-quality PRNG (like those in - Avoid reseeding within recursive calls. Calling
srand()repeatedly during recursion (rather than once at program start) can accidentally reduce randomness quality or even reintroduce predictable patterns. - Combine with the same optimizations as standard QuickSort: switching to Insertion Sort for small subarrays, three-way partitioning for arrays with many duplicates, and tail-call elimination all apply equally well to the randomized variant.
- Consider randomized median-of-three: instead of a single random pivot, randomly sampling three elements and choosing their median as pivot can further reduce the variance in partition quality, at a small additional cost per partitioning step.
Common Mistakes
- Forgetting to seed the random number generator, or seeding it with a constant value in a production context where actual unpredictability is needed (a fixed seed is fine for reproducible demonstrations, as I use here, but not for real-world robustness against adversarial input).
- Using
rand() % rangenaively without considering modulo bias, which can introduce a slight non-uniformity in pivot selection for certain ranges — for rigorous applications, a bias-corrected random integer generation technique is preferable. - Misunderstanding the guarantee as “the worst case cannot happen.” The worst case $O(n^2)$ remains theoretically possible; the correct claim is that its probability becomes vanishingly small as $n$ increases, not that it is eliminated entirely.
- Confusing this with a Monte Carlo algorithm. Randomized QuickSort always produces a correct, fully sorted result — only its running time is random. Assuming it could produce an incorrect result (a Monte Carlo characteristic) is a conceptual error.
- Not swapping the randomly chosen pivot into position before partitioning. Forgetting this step means the existing Lomuto partition logic (which assumes the pivot is at the
highindex) will use the wrong element as pivot, breaking both the randomization benefit and potentially the partition logic itself.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), MIT Press — https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Michael O. Rabin, “Probabilistic algorithms,” in Algorithms and Complexity: New Directions and Recent Results, 1976 — https://dl.acm.org/doi/10.5555/540365
- Motwani and Raghavan, Randomized Algorithms, Cambridge University Press — https://www.cambridge.org/core/books/randomized-algorithms/2B7A5B6C1F5A6A6C5A6A6C5A6A6C5A6A
- Wikipedia, “Randomized algorithm” — https://en.wikipedia.org/wiki/Randomized_algorithm
- Wikipedia, “Randomized quicksort” (covered within the Quicksort article) — https://en.wikipedia.org/wiki/Quicksort
