/ Published in: Java
It's no fun implementing QuickSort unless you can force it out of its blister-fast, O(n log n) speed and humiliate it with its worst-case, O(n^2) runtime. So that's what I set out to do.
My naive partition simply pivots around the low item, but my randomized partition defeats the sucky inputs by choosing a random pivot. (If you're interested in checking out a QuickSort which naively partitions until it hits an attempt to get it to run in quadratic time, check out IntroSort -- which simply fails over to Merge Sort when it exceeds its optimal recursion depth.)
My naive partition simply pivots around the low item, but my randomized partition defeats the sucky inputs by choosing a random pivot. (If you're interested in checking out a QuickSort which naively partitions until it hits an attempt to get it to run in quadratic time, check out IntroSort -- which simply fails over to Merge Sort when it exceeds its optimal recursion depth.)