News for hackers. Stuff that matters.
Re:Fastest sort of fixed length 6 int array by 5hoom on Wednesday August 24, 2011 @10:11AM (#2920717)
This is the sort of stuff that's great to read because you can't help but learn something.

I'd never never heard of sorting networks or oblivious sorting before, and it's good to see some answers other than "Quicksort!"

Re:Fastest sort of fixed length 6 int array by giardini on Wednesday August 24, 2011 @10:34AM (#2920803)
Surely by now you have read that quicksort's worst-case behavior is O(n2)?
Re:Fastest sort of fixed length 6 int array by 5hoom on Wednesday August 24, 2011 @10:47AM (#2920870)
But thats sort of the point.

I _have_ read about quicksort. Some of these other methods, not so much.

That for me makes this a useful and interesting story.

Re:Fastest sort of fixed length 6 int array by eru on Wednesday August 24, 2011 @03:02PM (#2922061)
If you use a randomized implementation the worst-case behaviour is expected to be O(n log n).

(Worst-case in the input, averaged over your random bits.)

Re:Fastest sort of fixed length 6 int array by giardini on Thursday August 25, 2011 @11:39PM (#2927298)
While using a randomized pivot implementation decreases the _likelihood_ of encountering a worst case, quicksort's worst-case behavior remains O(n2). See the last pages of

http://www.cs.duke.edu/~reif/courses/alglectures/skiena.lect...

I don't know that I've actually experienced a worst-case quicksort situation but I do know of a particular job using quicksort that ran far, far too long - indeed it never completed the quicksort step, because...

After 6 hours of sorting (all previous runs had completed the sort step in 40 minutes or less) we finally killed it, changed the sort implementation, fired it up again and never had the same problem again. It was an enterprise time-critical job running on a mainframe that simply had to complete within 24 hours of start.

Re:Fastest sort of fixed length 6 int array by eru on Monday September 05, 2011 @12:36PM (#2962660)
Depends on your definition of worst-case behaviour.