Quicksort: Difference between revisions

Revision as of 12:24, 12 June 2024

Revision as of 12:41, 12 June 2024

Line 263:

</math>

Solving the recurrence gives {{math|''C''(''n'') {{=}} 2''n'' ln ''n'' {{=}} 2''n'' ln 2 log₂ ''n'' ≈ 1.39''n'' log₂ ''n''}}.

This means that, on average, quicksort performs only about 39% worse than in its best case. In this sense, it is closer to the best case than the worst case. A [[comparison sort]] cannot use less than {{math|log₂(''n''!)}} comparisons on average to sort {{mvar|n}} items (as [[Comparison sort#Lower bound for the average number of comparisons|explained in the article Comparison sort]]) and in case of large {{mvar|n}}, [[Stirling's approximation]] yields {{math|log₂(''n''!) ≈ ''n''(log₂ ''n'' − log₂ ''e'')}}, so quicksort is not much worse than an ideal comparison sort. This fast average runtime is another reason for quicksort's practical dominance over other sorting algorithms.