There was some interest in my Java-based Quicksort project but that thread got locked.

To update: I was using an algorithm out of my book that used the right-most value as pivot. This led to the partitions being extremely unbalanced (8191 vs 1 in case of 2^13) and led to stack overflows starting at 2^13.

So I just updated my algorithm to utilize randomized quicksort; it chooses a pseudo-random element in the array and uses that as pivot. This solved my stack overflows as I was able to sort up to 2^20 for sorted, reverse sorted, and shuffled arrays with no problem.

So I guess I was lucky, Sekhmet, because my quicksort was performing faster than heapsort on the largest set (2^20). Here's some sample output.

Starting a HeapSort with n sorted numbers, where n = 1048576
Time to sort 1048576 sorted entries with Heapsort was 1015 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Starting a HeapSort with n reversed numbers, where n = 1048576
Time to sort 1048576 reversed entries with Heapsort was 886 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Starting a HeapSort with n shuffled numbers, where n = 1048576
Time to sort 1048576 shuffled entries with Heapsort was 1483 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
Starting a QuickSort with n sorted numbers, where n = 1048576
Time to sort 1048576 sorted entries with QuickSort was 396 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 1048576]
[(524288): 524289]
[(1048576): 1]
Starting a QuickSort with n reversed numbers, where n = 1048576
Time to sort 1048576 reversed entries with QuickSort was 400 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 857704]
[(524288): 190051]
[(1048576): 792221]
Starting a QuickSort with n shuffled numbers, where n = 1048576
Time to sort 1048576 shuffled entries with QuickSort was 481 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]

I have absolutely no clue about which you speak. Further evidence that most people are way smarter than I am.

I'm not into any complex sorting algorithms yet, but I did successfully complete the IPC assignment I mentioned in that thread with few issues. Now I know how to effectively share memory and communicate between processes to create a distributed workload. Yay!

You should experiment using the median-of-three method for choosing a pivot, and see how much faster you might be able to make it go :)

Very cool to see your results!

This is probably the last time you'll ever write these sorting algorithms, enjoy it while it lasts. :)

Cool, I think I will.

How do you choose the three? Beginning, middle, end? Three randoms?

Three randoms should work well. If you want to go all out, you could also implement switching to insertion sort once you're dealing with small arrays (around size 10 or so).

You can read up on it here: http://algs4.cs.princeton.edu/23quicksort/

Let me know if the median pivot works well!

A wise man once told me:

"A good programmer knows how to write good code,
but a great programmer knows how to steal good code."

;)

This is probably the last time you'll ever write these sorting algorithms

Unless he decides to interview for a programming job within 5 years after graduation.

Insomniac definitely had a pretty tricky in place array sort in their code test.