ALCOMFT-TR-02-128

Marianne Durand
Asymptotic Analysis of an Optimized Quicksort Algorithm
INRIA. Work package 5. May 2002.

Abstract: Jon Bentley and Doug McIlroy have implemented a fast quicksort for the C standard library in 1993. We consider here the average-case complexity in terms of number of comparisons, and give its asymptotic expansion up to constant order.

Postscript file: ALCOMFT-TR-02-128.ps.gz (83 kb).