---
title: "The Comparison-Sorting Lower Bound"
description: "Any sort that only compares pairs of elements is a decision tree with n factorial leaves, so its height is at least n log n. This is a statement about every possible algorithm, not about the ones anyb"
canonical: https://lightmysky.com/learn/computing/the-comparison-sorting-lower-bound-mt_7AfUsPV-jW
source: https://lightmysky.com/learn/computing/the-comparison-sorting-lower-bound-mt_7AfUsPV-jW.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`.

# The Comparison-Sorting Lower Bound

Any sort that only compares pairs of elements is a decision tree with n factorial leaves, so its height is at least n log n. This is a statement about every possible algorithm, not about the ones anybody has written.

Subject: Computing · Area: Algorithms & Data Structures · Ages 19 to 20
Page: https://lightmysky.com/learn/computing/the-comparison-sorting-lower-bound-mt_7AfUsPV-jW

## Ready when they can

- Draw the decision tree of a comparison sort on three elements and count its leaves
- Argue from the leaf count to a bound on the tree's height
- Explain how counting sort beats the bound without contradicting it

## Lesson: Why no comparing sort can beat n log n

A comparison sort learns only by comparing pairs of items. Picture its work as a decision tree, where each branch is one compare result and each leaf is one final order.

**Example.** Take three distinct items. They can arrive in 6 orders, which is 3 factorial, so the tree needs at least 6 leaves, one leaf per order. A tree of height 2 holds at most 4 leaves, so height 2 is not enough.

For n items there are n factorial orders, so any comparison tree needs n factorial leaves. Its height is at least log base 2 of n factorial, which grows like n log n. That height is a floor, called big-Omega, that every comparison sort must reach. Mergesort and heapsort touch that floor, so they are as fast as any comparison sort can ever be.

**Tip.** Counting sort can run faster because it changes the rules and reads values instead of comparing pairs. That beats the floor without breaking it, since the floor only covers comparing sorts.

**Recap.** Comparing sorts need n factorial leaves, so they cost at least n log n, and only non comparing methods can dodge that floor.

## Practice

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

## Needs first

- [Counting Outcomes with the Product Rule](https://lightmysky.com/learn/mathematics/counting-outcomes-with-the-product-rule-mt_74gSbYIG8p)
- [Randomised Quicksort and Expected Running Time](https://lightmysky.com/learn/computing/randomised-quicksort-and-expected-running-time-mt_fcKF7zfzpX)
- [Proof by Contradiction and Counterexample](https://lightmysky.com/learn/mathematics/proof-by-contradiction-and-counterexample-mt_pbFTv4v6k8)
- [Statements, Quantifiers and Negation](https://lightmysky.com/learn/mathematics/statements-quantifiers-and-negation-mt_S5NvyPxEZ_)

## Opens up

- [Heaps and Priority Queues](https://lightmysky.com/learn/computing/heaps-and-priority-queues-mt_W-ofiMiXWs)