gurne...@efn.org (John-Mark Gurney) writes: > Christopher Seiwald scribbled this message on Aug 18: > > It's a pretty straightforward change to bypass the insertion sort for > > large subsets of the data. If no one has a strong love for qsort, I'll > > educate myself on how to make and contribute this change. > > why don't you implement this w/ the 5 element median selection qsort > algorithm? my professor for cis413 talked about this algorithm and > that it really is the fastest qsort algorithm... I don't have any > pointers to a paper on this... but I might be able to dig some info up > on it if you are interested...
I don't think the point is eliminating worst-cases, but optimizing common cases, which in this case caused more worst-cases and thus needs fixing. Besides, the median selection chooses among more than 3 elements already (but only when the data set is large enough). For fixing worst cases, an introspective sort might be a good idea, i.e. do a quick sort but fall back to heap sort if a certain depth is exceeded (you know you're losing when the depth exceeds log n). This also has another advantage - if you limit the depth of the sort, you don't need to use the cpu stack for state, you can allocate a fixed-size array for the purpose. This probably isn't a real performance advantage for a C qsort implementation because of the overhead of calling cmp. It does, however, guarantee that sorting uses a reasonable amount of stack. Such an assumption isn't portable when using qsort(3), though. Expect to die if you do large qsorts from threads with small thread stacks. To Unsubscribe: send mail to majord...@freebsd.org with "unsubscribe freebsd-hackers" in the body of the message
