Subj : Re: Arranging the keys problem
To   : comp.programming
From : Googmeister
Date : Fri Sep 30 2005 05:13 am


Lars Weber wrote:
> Hi Willem,
>
> You're wrong.
> Quicksort is not of linear runtime.
> In worstcase it's O(n=B2) and in the average it's O(n log n).
>
> Have a look here to get more information:
> http://en.wikipedia.org/wiki/Sorting_algorithms#List_of_sorting_algorithms

Actually, good implementations of quicksort (e.g., those that use
3-way partitioning / Dutch National Flag) are O(n) worst-case if
there are only a constant number of distinct elements.

Unfortunately, some textbook implementations are quadratic
when there are a constant number of distinct elements.

.