---
title: "Randomised Quicksort and Expected Running Time"
description: "Quicksort partitions around a pivot, and its worst case is quadratic. Choosing the pivot at random makes the bad case a matter of luck rather than of input, and the expected running time is n log n wh"
canonical: https://lightmysky.com/learn/computing/randomised-quicksort-and-expected-running-time-mt_fcKF7zfzpX
source: https://lightmysky.com/learn/computing/randomised-quicksort-and-expected-running-time-mt_fcKF7zfzpX.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Randomised Quicksort and Expected Running Time

Quicksort partitions around a pivot, and its worst case is quadratic. Choosing the pivot at random makes the bad case a matter of luck rather than of input, and the expected running time is n log n whatever the adversary supplies.

Subject: Computing · Area: Algorithms & Data Structures · Ages 19 to 20
Page: https://lightmysky.com/learn/computing/randomised-quicksort-and-expected-running-time-mt_fcKF7zfzpX

## Ready when they can

- Partition an array around a pivot in place and state the invariant of the partition loop
- Construct the input that makes a fixed-pivot quicksort quadratic
- Explain what randomising the pivot changes, and what it does not

## Lesson: Quicksort without the worst case

Quicksort is divide and conquer in three moves. Partition the array around one pivot so everything smaller sits left and everything bigger sits right, then conquer each side by running the same method on it. Small sides are solved directly, and the sorted pieces join for free since the pivot already sits between them.

**Example.** Partitioning is one linear scan with two fingers. Finger j walks left to right over each item, while finger q marks the end of the small region. The invariant never breaks: everything left of q is smaller than the pivot. When j finds a small item, it swaps it just past q and both fingers advance; at the end the pivot swaps into place at q.

Fixed pivots have a nightmare: a sorted input where every pick is the smallest or largest remaining item. Then one side takes everything and the other takes nothing, so the problem shrinks by a single item each round and the total work grows like 1 plus 2 plus dot dot dot plus n, which is quadratic. Picking the pivot at random turns this nightmare into mere bad luck: no input can force it anymore, the worst case still exists but grows unlikely, and the expected running time is n log n whatever the adversary supplies.

**Tip.** Keep straight what randomising changes and what it does not. It changes who chooses the bad case: luck, not the input. It does not remove the quadratic worst case, speed up the linear partition scan, or help if the pivot generator itself is rigged.

**Recap.** Partition in one scan, expect luck instead of fearing inputs, and remember the worst case still lurks underneath.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Loop Invariants and Proving an Algorithm Correct](https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns)
- [Expected Value and Variance of a Discrete Random Variable](https://lightmysky.com/learn/mathematics/expected-value-and-variance-of-a-discrete-random-variable-mt_PFdo0Nm3FP)
- [Divide and Conquer as a Design Method](https://lightmysky.com/learn/computing/divide-and-conquer-as-a-design-method-mt_YITRNb-HTE)

## Opens up

- [The Comparison-Sorting Lower Bound](https://lightmysky.com/learn/computing/the-comparison-sorting-lower-bound-mt_7AfUsPV-jW)