3 ms·
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 befor
by 5hoom 15y ago
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!"
- giardini 15y agoSurely by now you have read that quicksort's worst-case behavior is O(n2)?
- 5hoom 15y agoBut 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.
- eru 15y agoIf 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.)
- giardini 15y agoWhile 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.lectures/lecture5.pdf 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.
- eru 15y agoDepends on your definition of worst-case behaviour.