MENTAL MODEL · M13138

Comparison Sorts

TechnicalHigh supportAlgorithms

Included

Updated 2026-08-17

Loading revision record…

INTRODUCTION

English translation pending.

CORE DEFINITION

Comparison sorts are algorithms that determine order solely by asking whether one element is less than another. Quicksort, devised by Tony Hoare in 1959, merge sort, described by John von Neumann in 1945, and heapsort, published by J. W. J. Williams in 1964, are the standard examples. A decision-tree argument shows that distinguishing all n! possible orderings requires at least a number of comparisons proportional to n log n, so no comparison sort can beat that bound in the worst case. The bound applies only to comparison-based methods: counting sort and radix sort sidestep it by using the values themselves as addresses.

SCAFFOLDING EFFECT

psychology

Reduce cognitive load

- Algorithm choice: Check whether values can be used as addresses before defaulting to a comparison sort. - Cost estimate: Use the n log n bound to sanity-check whether a sorting step can fit your budget. - Data-shape check: Ask whether the input is nearly sorted or adversarially ordered before picking an implementation.

anchor

Anchor fast decisions

Each comparison yields at most one bit of information, because it can only answer yes or no. There are n factorial possible orderings, so identifying the correct one requires at least log base two of n factorial comparisons, and Stirling's approximation turns that into a bound proportional to n log n. Any comparison-based algorithm therefore has to spend at least that many comparisons in the worst case, no matter how cleverly it chooses which pair to compare.

MINIMUM ACTION

In progress 0/1

Practice this model in one real situation:

Write down the number of records and check whether n log n comparisons fit your time budget. 2. Test whether the keys can be used directly as addresses, which would allow counting or radix sort. 3. Inspect the input distribution for near-sortedness, duplicates, or adversarial ordering. 4. Pick the algorithm whose worst case you can tolerate, not just the one with the best average. 5. Measure actual runtime on a realistic input before committing to the choice.

Check to track your progress (stored locally)

Learning progress0%

account_treeGenealogyexpand_more

menu_bookReferencesexpand_more

Source support: Explicit

link
github.comhttps://github.com/kcchien/model-thinkingZH · Explicit
verified

RELATED MODELS