Shuffle an array so that every permutation is equally likely.

Use Fisher-Yates: for i from n - 1 down to 1, pick j uniformly from 0 to i inclusive and swap a[i] and a[j]. There are n × (n - 1) × ... × 2 = n! equally likely sets of choices, one for each permutation, so every permutation has probability 1 / n!. Time is O(n) and extra space is O(1). Picking j from the whole array instead gives n^n choices, which cannot divide evenly among n! permutations, so it is biased.

What happens if the shuffle picks j from 0 to i - 1 instead of 0 to i?

That is Sattolo's algorithm. There are (n - 1) × (n - 2) × ... × 1 = (n - 1)! choices, and every result is a single cycle, so no element ever stays in its original position. Only (n - 1)! of the n! orders can appear, so it is not a uniform shuffle. Use it only when you need a cyclic permutation, for example "secret Santa with nobody drawing themselves".

Pick k items uniformly from a stream of unknown length.

Keep the first k items. For item number i after that (counting from 1), pick j uniformly from 0 to i - 1, and if j is less than k, put the item at position j. The item enters with probability k / i, and a kept item survives step j with probability 1 - 1 / j, so the product telescopes to k / n for every item. Time is O(n) and memory is O(k). If n is less than k, you return all items.

What is the difference between a Las Vegas and a Monte Carlo algorithm?

A Las Vegas algorithm always returns a correct answer, and only its running time is random (randomized quicksort). A Monte Carlo algorithm has a fixed running time but may return a wrong answer with a small probability that you can lower by repeating it (a randomized primality test). A Monte Carlo algorithm can be turned into Las Vegas only if you can check the answer cheaply.

Pick a random node from a linked list of unknown length, using O(1) memory.

Reservoir sampling with k = 1. Keep the first node. For the i-th node (counting from 1), replace the kept node with probability 1 / i. After the last node, each node has been kept with probability (1 / i) × (i / (i + 1)) × ... × ((n - 1) / n) = 1 / n. Time is O(n) and space is O(1). The list is read once, which is why it works for streams too.

Pick an index with probability proportional to its weight.

Build an array of prefix sums of the weights, pick a random number from 1 to the total, and binary search for the first prefix that is at least the number. Building takes O(n), each pick takes O(log n), and space is O(n). For many picks from fixed weights, the alias method gives O(1) per pick after O(n) setup.

Why does quicksort use a random pivot, and what is its running time?

A fixed pivot rule such as "always the first element" has a worst case, for example an already-sorted input, that costs O(n²). A random pivot means no particular input is always bad. The expected time is O(n log n) over the random choices, with expected stack depth O(log n). The worst case is still O(n²), but its probability is tiny.

Randomized Algorithms

intermediate · 25 min · Last reviewed 31 Oct 2026 · by TheLearningLoop Team

Key takeaways

A shuffle of n items is fair only if it can produce every one of the n! orders in the same number of ways. Fisher-Yates does; swapping with a position from the whole array does not.
Reservoir sampling keeps a uniform random sample of a stream of unknown length in O(k) memory: item i replaces a kept item with probability k / i.
A random pivot gives quicksort and quickselect their good expected time for every input. Secrets need a cryptographically secure generator, not an ordinary one.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use a randomized algorithm

Use randomness when you need to:

Shuffle items so that every order is equally likely: a deck of cards, a playlist, the order of test cases, a random sample of users.
Pick a fair random sample from a stream whose length you do not know, using fixed memory: reservoir sampling.
Avoid a bad worst case that an adversary or an unlucky input could trigger, as in quicksort with a random pivot.
Break ties or spread load evenly, as in random choice between two servers.

Use something else when:

You need cryptographic randomness (keys, tokens, passwords): use your language's secure random source, not the ordinary generator.
You need repeatable results (tests, simulations): use a seeded generator and record the seed.
You need a sort order that is stable and known: do not shuffle, sort.
A deterministic algorithm is simple and fast enough.

Do not write your own shuffle or generator in production. Use Collections.shuffle, std::shuffle, random.shuffle, rand.Shuffle or the like (see the real-world section). Writing Fisher-Yates by hand is for learning and interviews, and a classic place for a subtle bug.

How randomized algorithms work

There are two families. A Las Vegas algorithm always gives a correct answer and only its running time is random (randomized quicksort always sorts correctly). A Monte Carlo algorithm runs in a fixed time but its answer may be wrong with a small, known probability (estimating a value by random samples). Everything on this page except the Monte Carlo example in the real-world section is Las Vegas style, where "random" affects the path taken, not the correctness.

A randomized algorithm uses random choices as part of its logic. The skill is not "adding randomness" but making sure the random choices produce the distribution you promised. The classic mistake is a shuffle that looks random but is biased.

Fairness rule: a shuffle of n items must be able to produce each of the n! orders in exactly the same number of ways.

Fisher-Yates goes from the last position down to 1. At position i it picks a random position j from 0 to i (including i) and swaps. Position i is then final. The number of choices is n × (n-1) × ... × 2 = n!, one per order, so every order is equally likely.
A naive shuffle swaps each position with a random position from the whole array. That makes n × n × ... × n = nⁿ equally likely choices. For three items that is 27, and 27 cannot be split evenly among 6 orders, so some orders come out more often than others. It is biased.
Reservoir sampling keeps one (or k) items from a stream. Item number i replaces the kept item with probability 1 / i. An early item starts with a high chance of being kept but has many later chances of being replaced. A late item has a low chance of being kept at first but few chances of being replaced. The two effects cancel exactly, so every item ends up kept with the same probability 1 / n.

Try it

Start with the biased shuffle and Count every possible outcome. Then compare the others.

Randomized Algorithms

Step 1 of 2 · Press Space to play, arrow keys to step

AlgorithmShow

Array

Initial state. Shuffle A B C so that every one of the 6 orders is equally likely.

step:: 0
random numbers used:: 0

Speed

Things to try:

Choose Naive shuffle and Count every possible outcome. There are 27 equally likely choices. Three orders appear 5 times and three appear only 4 times: it is biased. Now choose Fisher-Yates and see every one of the 6 orders appear exactly once.
Choose Fisher-Yates and One run, step by step. Watch position 2, then position 1, get a random swap partner. Each position is final once it has been processed.
Choose Reservoir sampling and Count every possible outcome. Each of the 4 stream items is kept in exactly 6 of the 24 outcomes, so each has probability 1 in 4.
Watch the most likely and least likely counters under the naive shuffle (5 and 4). The gap is the bias. Under Fisher-Yates both counters are 1.
Choose Reservoir sampling and One run, step by step a few times: the kept item changes often early on and rarely late, yet the final answer is equally likely to be any item.
One run proves nothing about fairness. Only counting every outcome does.

A dry run on three items

Shuffle A B C. Fisher-Yates handles position 2, then position 1, so there are 3 × 2 = 6 choices:

Choice at position 2	Array after it	Choice at position 1	Final order
j = 0	`C B A`	j = 0	`B C A`
j = 0	`C B A`	j = 1	`C B A`
j = 1	`A C B`	j = 0	`C A B`
j = 1	`A C B`	j = 1	`A C B`
j = 2	`A B C`	j = 0	`B A C`
j = 2	`A B C`	j = 1	`A B C`

All six orders appear exactly once, so each has probability 1/6.

The naive shuffle swaps each of the 3 positions with any of the 3 positions, giving 3 × 3 × 3 = 27 equally likely choices. Counting what they produce gives BCA, BAC and ACB five times each, and CAB, CBA and ABC four times each (3 × 5 + 3 × 4 = 27). Since 27 is not a multiple of 6, equal counts are impossible. BCA has probability 5/27 (about 18.5%) and ABC has 4/27 (about 14.8%).

Reservoir sampling of one item from A B C D. Take B: it enters at step 2 with probability 1/2, survives step 3 with probability 2/3 and survives step 4 with probability 3/4. The product is 1/2 × 2/3 × 3/4 = 1/4. The same product for any other item is also 1/4.

Randomized algorithm operations: shuffle, sample and choose a pivot

Fisher-Yates shuffle.

Start at the last position i = n - 1.
Pick j at random from 0 to i (both included).
Swap a[i] and a[j].
Move i down by one, and repeat until i is 1.

Reservoir sampling (one item).

Keep the first item.
For item number i (counting from 1), pick a random number from 1 to i. If it is 1, replace the kept item with this one.
After the last item, the kept item is a uniform random choice.

Reservoir sampling (k items). Fill the reservoir with the first k items. For item number i after that, pick a random j from 0 to i - 1. If j is less than k, put the item at position j of the reservoir.

Random pivot in quicksort or quickselect. Pick the pivot position at random. No fixed input can force the worst case, because the pivot is not known in advance. The expected time is O(n log n) for sorting and O(n) for quickselect.

Why the bounds hold.

Reservoir sampling with k items. The item at position i (counting from 1, with i above k) enters with probability k / i. A kept item is replaced at step j with probability 1 / j (the new item is picked with k / j, and it lands on this particular slot with 1 / k), so it survives with (j - 1) / j. The product over steps i + 1 to n telescopes to i / n, and k / i × i / n = k / n. The first k items are kept for certain and survive each later step the same way, which also gives k / n.
Random pivot. A pivot that lands in the middle half of the sorted order has probability 1/2. When it does, each side holds at most three quarters of the items, so the problem shrinks by a constant factor. On average two tries are needed per shrink, so the depth is O(log n) levels of O(n) work.

A note on random numbers. To get a number from 0 to i you must draw uniformly from exactly i + 1 values. Taking an ordinary random number and using % (i + 1) slightly favours small values unless the range divides evenly. Library functions such as rand.Shuffle or random.randrange handle this for you.

A shuffle must pick from 0 to i, not from the whole array. This is the interview fact: that single detail separates a correct shuffle from a biased one.

Randomized algorithm time complexity

Algorithm	Time	Space	Guarantee
Fisher-Yates shuffle	O(n)	O(1) extra	Every order equally likely
Naive shuffle (swap with any position)	O(n)	O(1) extra	Biased: not every order is equally likely
Reservoir sampling, one item	O(n)	O(1)	Each of `n` items kept with probability 1/n
Reservoir sampling, `k` items	O(n)	O(k)	Each item kept with probability k/n
Randomized quicksort	O(n log n) expected, O(n²) worst	O(log n) expected stack	Worst case is very unlikely, whatever the input
Randomized quickselect	O(n) expected, O(n²) worst	O(1) extra	Same idea as quicksort

n is the number of items and k the sample size. "Expected" means averaged over the random choices, not over the inputs, so a hostile input cannot hurt it.

Randomized algorithms vs other approaches

Job	Fisher-Yates	Sort by random key	Reservoir sampling	Deterministic approach
Shuffle an array	O(n), fair	O(n log n), fair if keys are unique	Not applicable	Not possible
Sample `k` from a known-size list	O(k) with partial shuffle	O(n log n)	O(n)	Pick first `k` (not random)
Sample `k` from a stream of unknown length	Not possible	Not possible	O(n), O(k) memory	Store everything: O(n) memory
Avoid worst-case quicksort	Not applicable	Not applicable	Not applicable	Median of medians: O(n), complex
Repeatable results	With a seeded generator	With a seeded generator	With a seeded generator	Always
Easy to get wrong	Off-by-one in the range	Sorting by a random comparator is biased	Probability `1/i`	Simple

n is the number of items. Fisher-Yates wins for shuffling, and reservoir sampling wins when the data does not fit in memory or its length is unknown. Never sort with a random comparator such as sort(() => Math.random() - 0.5): it is biased and its behaviour depends on the sort algorithm.

How to recognise a randomized-algorithm problem

Look for these phrases in a problem statement:

"Every permutation / subset / element must be equally likely" means a fairness argument, usually Fisher-Yates or a sampling method.
"Stream", "unknown length", "cannot store everything" or "one pass" means reservoir sampling.
"Pick with probability proportional to a weight" means prefix sums plus binary search (see the interview section).
"Expected time", "no input should be bad" or "adversarial input" means a random pivot or random hash.
"Approximately", "estimate" or "with high probability" means a Monte Carlo method.

Then ask three questions. What distribution do I promise? Can I count the equally likely choices? Does the answer have to be exact (Las Vegas) or may it be wrong rarely (Monte Carlo)?

Edge cases to check

0 or 1 items. Fisher-Yates loops from n - 1 down to 1, so it does nothing and returns the input, which is the only possible order.
k at least n in reservoir sampling. The reservoir never fills past the stream, so you get every item. Decide whether that is allowed.
Empty stream. One-item reservoir sampling has nothing to return, so return "none" explicitly.
Duplicate values. The shuffle treats positions, not values, so equal values are fine, but the number of distinct outputs is smaller than n!.
Sorted or all-equal input to randomized quicksort. Sorted input is no longer special. A plain two-way partition on all-equal input still degrades, so use three-way partitioning.
Repeatability. A fixed seed gives the same result every run, which is what tests need, and what secrets must never have.

Common mistakes

Picking j from the whole array in a shuffle (n^n choices, biased), or from 0 to i - 1 (excludes i, which is Sattolo's algorithm: only single-cycle orders, so no item stays in place).
Sorting with a random comparator such as sort(() => Math.random() - 0.5): inconsistent comparisons, biased result that depends on the sort algorithm.
Using probability 1 / n or a fixed 1 / 2 in reservoir sampling instead of 1 / i for the i-th item.
Counting from 0 and using 1 / i for the first item. The first item must be kept with probability 1.
Using an ordinary generator for passwords, keys or tokens.
Re-seeding the generator inside a loop (for example with the clock), which repeats values.
Trusting a single run to show fairness. Fairness is a statement about all outcomes, which is why the simulation counts them.

How to explain randomized algorithms in an interview

Say what distribution you promise ("every permutation equally likely") and show why with a counting argument: Fisher-Yates has n! equally likely choices, so each order has probability 1 / n!.
For reservoir sampling, give the probability proof: item i is kept at step i with probability 1/i, then survives each later step j with probability 1 - 1/j; the product telescopes to 1/n.
Say "expected" versus "worst case" for randomized quicksort and why a hostile input cannot target it.
Add a practical note: use the library for shuffles, a secure generator for secrets, and a fixed seed in tests.

Where you meet randomized algorithms in real systems

Randomness is in games, tests, load balancers, analytics and security. Here are three of them drawn out, the first with code you can run, then more examples.

Example 1: Sampling log lines from a stream

A service writes millions of log lines and an engineer wants a small, fair sample to inspect without storing everything. The stream has no known length, so a fixed fraction (every 100th line) would be biased by the pattern of the data. Reservoir sampling keeps exactly k lines in memory and guarantees that every line seen so far has the same chance of being among them. Open the example below to see the picture and the code.

Code: Fisher-Yates shuffle and reservoir samplingTime O(n)Memory O(1) and O(k)

The first k items fill the reservoir. Each later item replaces a random slot with probability k divided by the number of items seen so far. The sample is fair at every moment.

# Fisher-Yates shuffle and reservoir sampling, with a tiny fixed-seed random generator so the
# output is the same every run and in every language. In real code use your language's generator.
# Fisher-Yates: time O(n), extra memory O(1). Every one of the n! orders is equally likely.
# Reservoir sampling (Algorithm R): time O(n) for a stream of n items, memory O(k) for k kept items.

class Lcg:
    def __init__(self, seed):
        self.state = seed

    def below(self, k):                 # a number from 0 to k-1
        self.state = (self.state * 1103515245 + 12345) & 0x7FFFFFFF
        return (self.state >> 8) % k    # use the higher bits, which are better than the lowest ones

def shuffle(items, rng):
    a = list(items)
    for i in range(len(a) - 1, 0, -1):  # from the end down to 1
        j = rng.below(i + 1)            # j is from 0 to i, never beyond i: this is what keeps it fair
        a[i], a[j] = a[j], a[i]
    return a

def reservoir_sample(stream, k, rng):
    kept = []
    for i, x in enumerate(stream):      # we only ever look at one item at a time
        if i < k:
            kept.append(x)              # the first k items fill the reservoir
        else:
            j = rng.below(i + 1)        # keep the new item with probability k / (i + 1)
            if j < k:
                kept[j] = x
    return kept

print("shuffle:", *shuffle(range(1, 9), Lcg(42)))
print("sample:", *reservoir_sample(range(1, 11), 3, Lcg(42)))

Each version uses a tiny fixed-seed generator so that its output is the same every run and in every language (real code would use the language's own generator, which also avoids the slight bias of using % on a random number). Every version was written to print exactly this, and the Python and C++ versions were compiled and run while checking this page. The output is the shuffle 8 6 3 5 1 2 4 7 of 1 to 8 and the sample 8 6 9 of 3 items from 1 to 10.

Example 2: A fair shuffle for a music player

A playlist shuffle that favours some orders would be noticed by listeners ("it always plays this song after that one"). Fisher-Yates guarantees every order is equally likely. Many players also add a rule so that the same artist does not play twice in a row, which is a constraint on top of the fair shuffle, not a replacement for it.

Starting from the last position, each song is swapped with a random song at or before it. After each step the finished positions on the right (highlighted) never change again.

Example 3: Picking between two random servers

A load balancer that picks two servers at random and sends the request to the less busy one keeps queues far more even than choosing one at random, with almost no extra work. The result is often called the "power of two choices" and is why randomness appears in load balancers.

Illustrative picture: the balancer picks two servers at random, compares their current load, and sends the request to the less loaded one.

More real-world scenarios

4. Games and simulations

Shuffling a deck, rolling dice and spawning enemies need fair randomness. Competitive games and online casinos also need it to be unpredictable, which means a secure generator.

5. Randomised quicksort and quickselect

Choosing a random pivot makes the expected time O(n log n) for any input. This protects a service from inputs crafted to hit a fixed-pivot worst case. A short Python version of both algorithms (the pivot is the only random choice):

import random

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[random.randrange(len(a))]            # random pivot: no input is always bad
    return (quicksort([x for x in a if x < pivot])
            + [x for x in a if x == pivot]         # three-way split, so equal values are handled
            + quicksort([x for x in a if x > pivot]))

def quickselect(a, k):                             # k-th smallest, counting from 0
    pivot = a[random.randrange(len(a))]
    below = [x for x in a if x < pivot]
    equal = [x for x in a if x == pivot]
    if k < len(below):
        return quickselect(below, k)
    if k < len(below) + len(equal):
        return pivot
    return quickselect([x for x in a if x > pivot], k - len(below) - len(equal))

data = [5, 3, 8, 3, 9, 1, 7]
print(quicksort(data))                # [1, 3, 3, 5, 7, 8, 9]
print(quickselect(data, 3))           # 5

This version copies lists for clarity, so it uses O(n) extra space per level. The in-place version uses O(log n) expected stack for quicksort, as in the table in the lesson.

6. A/B testing and rollouts

Users are assigned to a variant by a hash or a random draw, so that each variant gets a fair, comparable sample. A rollout to 5% of users uses the same idea.

7. Load balancing and retries

Random choice spreads work. Random delays added to retries (jitter) stop many clients from retrying at the same instant after an outage.

8. Machine learning

Training shuffles the data each epoch, mini-batches are sampled at random, and techniques such as dropout switch parts of a network off at random.

9. Testing and fuzzing

Property-based tests and fuzzers generate random inputs to find bugs a human would not think of. A recorded seed lets you reproduce a failure.

10. Cryptography

Keys, nonces and session tokens must come from a cryptographically secure source. A normal generator such as a linear congruential generator is predictable and must never be used for secrets.

11. Monte Carlo methods

Estimating a value by random sampling, such as the probability of a complex event or the area of an odd shape, is useful when an exact calculation is too hard.

12. Hashing and data structures

Skip lists choose each node's height at random, treaps give each node a random priority, and hash tables can pick a random hash function to defeat adversarial keys.

Language standard libraries

Every mainstream language has a shuffle or at least a seedable random generator. Use the secure generator for anything secret.

Language	Shuffle and sampling	Secure random	Notes
Java	`Collections.shuffle`, `Random`, `ThreadLocalRandom`	`SecureRandom`	`Collections.shuffle` is a Fisher-Yates shuffle.
C++	`std::shuffle` with `<random>` engines such as `std::mt19937`	`std::random_device` (platform dependent)	`std::random_shuffle` was removed in C++17.
C#	`Random.Shuffle` (.NET 8 and later), `Random`	`RandomNumberGenerator`	Older code writes Fisher-Yates by hand.
Rust	`rand` crate: `SliceRandom::shuffle`, `choose_multiple`	`rand::rngs::OsRng`	Not in the standard library; `rand` is the usual crate.
Python	`random.shuffle`, `random.sample`, `random.choice`	`secrets` module	`random` is not safe for secrets.
Go	`rand.Shuffle` in `math/rand` and `math/rand/v2`	`crypto/rand`	Seed `math/rand` explicitly in older versions for repeatable results.
JavaScript	`Math.random` only (no built-in shuffle)	`crypto.getRandomValues`	Write Fisher-Yates; never sort with a random comparator.
Kotlin	`list.shuffled()`, `shuffle()`, `Random`	Java's `SecureRandom`	Wraps Java's shuffle on the JVM.

The takeaway from the table: shuffles are built in nearly everywhere, but reservoir sampling is not, so you write it yourself. For secrets, always use the secure source.

The takeaway

Whenever a system needs a fair random order or sample, look for Fisher-Yates for shuffling and reservoir sampling for streams, and check that the random choices give every outcome equal probability. When it needs secrets, it uses a secure random source, not an ordinary generator.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Shuffle an array so that every permutation is equally likely.
medium
2.
What happens if the shuffle picks j from 0 to i - 1 instead of 0 to i?
hard
3.
Pick k items uniformly from a stream of unknown length.
medium
4.
What is the difference between a Las Vegas and a Monte Carlo algorithm?
easy
5.
Pick a random node from a linked list of unknown length, using O(1) memory.
medium
6.
Pick an index with probability proportional to its weight.
medium
7.
Why does quicksort use a random pivot, and what is its running time?
easy

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Probabilistic Data Structures

Choosing a Pattern from the Constraints

Topics:RandomShuffleFisher yatesReservoir samplingSamplingMonte carloProbability