Today I spared sometime running some experiments around quick sort just for fun.
I implemented one by myself recursively, found another in-place one here which I name it InternetQuickSort as one Google Search returns almost this same implementation (I am not certain about the intellectual property ownership here though) and the third one is using our DualPivot Quick Sort under Arrays java utility class. About my implementation, it is a dump one as I have no intention to compete with other which got spent a huge amount of time of many smart people in order to optimize it, my implementation is only served as an example of how bad it is and in order to see how good the other two are.
In psuedo code, my implementation is like
# Step 1: Pick a pivot value by getting the mean of three elements at startingPos, endingPos and mid point
# Step 2: Loop from startingPos to endingPos and form two arrays, one with elements greater than pivotVal and one with element smaller than pivotVal
# Copy back the two arrays into the original arrays
# Recursively call MySort on two sub arrays by changing startingPos and endingPos
Below are the experiment setup
System: runs on a Intel Core i5 3Ghz x 4, 64 bits, Java 7
Input: My experiments are conducted on arrays size starting of 250,000 element and incremental step of also 250,000 element, 25 steps
I have made a simple chart here QuickSortBenchmark
Interestingly, most of the case the InternetQuickSort version outperforms the DualPivotQuickSort but they are quite close to each other. My implementation doesn’t give a clear trend with quite large fluctuation range. However both mine and Dual Pivot QuickSort have a spike in performance when the number of element around 4 millions while the Internet Quick Sort version doesn’t encounter that at all.
Will have some more update about this.