Intel® Software Network

It is not clear from the problem statement how much we can deviate from the quicksort algorithm.

On the worst case (file already sorted), quicksort have a O(N^2) complexity.

Current STL sort implementations are using introsort (an enhanced version of quicksort).

I assume that we should keep the original quicksort algorithm without any modifications.

The "bulk" of the sorting must be within your application and be implementing the quicksort algorithm.  Running a single partition of the data and then allowing some library routine to sort each "half" is not going to be a valid entry.  Running a direct comparison and swap, if needed, when the portion to sort contains 2 or fewer items is acceptable. 

If you don't want to run quicksort to the point where there are no items in the data to be sorted, then what will the judges consider to be an acceptable cutoff?  Somewhere in between the two cases above, certainly, but closer to the latter.

Documentation of any deviations from the original code and rationale for such changes can only help your case.

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

Since we are instructed to implement the most part of the algorithm as quicksort, I think  judges should use randomized input files to get the average run time. Is this a safe assumption?

Yes, that is how judging will be done.  Each code will be run on the same input files.

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K

I just modified the algorithm according to the in-place version in page
http://en.wikipedia.org/wiki/Quicksort , and use the medium of left, right, and middle as the pivot. After that, the worst case is gone. Just a tip for those who really want to avoid the worst cases.

I think worst case depends upon the pivot. It is somewhat possible to create a worst case scenario for any choice of pivot element. for example choosing median of left, right and middle as a pivot, can be attacked by median-of-3 killer sequences, invented by David Musser. Google it for more information.

Therefore i humbly request the judges to consider this while creating random data sets for testing. The choice of pivot should not be a criteria for declaring a particular entry better.

Using a random pivot element makes quicksort run in expected time O(n Log n), which means that for ever larger array sizes, the probability for worse complexity (maximum n^2) decreases to 0. For each other pivot strategy, you can devise an array that results in worst case complexity rather easily.

Remark: Parallelized versions of quicksort can run in O(n). Assuming you have infinite computing resources, you can even parallize the partition step so that complexity goes down to O(log n)

May be it will be used for participants:
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
(Describes how to find the worst case for different pivot methods)