Smoothness and decay properties of the limiting Quicksort density function

James Allen Fill (Johns Hopkins Univ.); Svante Janson (Uppsala Univ.)

Smoothness and decay properties of the limiting Quicksort density function

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv math/0005235 v1 pith:SHYN73VZ submitted 2000-05-23 math.PR cs.DS

James Allen Fill (Johns Hopkins Univ.) , Svante Janson (Uppsala Univ.) This is my paper · ORCID

classification math.PRcs.DS

keywords boundeddecaydensitylimitingprovequicksortanalysisarray

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and infinitely differentiable density f, and that each derivative f^{(k)} enjoys superpolynomial decay at plus and minus infinity. In particular, each f^{(k)} is bounded. Our method is sufficiently computational to prove, for example, that f is bounded by 16.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Using Large Language Models to Study Mathematical Practice
math.HO 2025-06 conditional novelty 6.0 of 10

An LLM-assisted corpus study finds that roughly 3% to 12% of 5,000 arXiv math papers contain clear or borderline appeals to mathematical explanation, with frequency varying by subfield.

Pith tools