"Jérôme M. Berger" wrote: > Steven Schveighoffer wrote: >> On Thu, 07 Oct 2010 16:23:47 -0400, Rainer Deyke <rain...@eldwood.com> >> wrote: >> >>> On 10/7/2010 13:57, Andrei Alexandrescu wrote: >>>> On 10/7/10 14:40 CDT, bearophile wrote: >>>>> Another solution is just to accept O(n) as the worst complexity for >>>>> the "in" operator. I don't understand what's the problem in this. >>>> >>>> That means we'd have to define another operation, i.e. "quickIn" that >>>> has O(log n) bound. >>> >>> Why? >>> >>> I can't say I've ever cared about the big-O complexity of an operation. >> >> Then you don't understand how important it is. > > If big O complexity is so important, then why does everyone use > quicksort (which is O(n**2)) and not heap sort or merge sort (which > are O(n*log(n)))? > > Jerome
For average case big O and dwarfing heap/merge sort in the constant factor. But in fact its not totally true that everyone uses quicksort pur sang: most sort implementations deal with the worst case of quicksort, by switching to heapsort for example. It is exactly because of this behavior.
