Possible Duplicate:
When are two algorithms said to be “similar”?

Generic Overview of promblem:
I read somewhere once that a quicksort could be done without recursion in O(1) space overhead. I thought about it for a while, and then coded a version of quicksort that uses O(1)-space overhead (eg: in-place). However, since it lacks a lot of the metainformation that quicksort normally has available (beginning and ending of each chunk to recurse down), I had to add a pre-step to "format" the data a specific way so that the rest of the quicksort can correctly determine where each chunk begins and ends. When discussing this algorithm in StackOverflow chat, R.Martinho speculated that this is no longer a quicksort due to the requirement of the prestep.

Overview of Algorithm:
The general idea is that for each chunk of data, the algorithm picks a pivot P from the chunk (the first in my case), and partitions the data on P into two chunks: data less than P and data greater than P. It then puts the data in the order of [P][less than P][Greater than P]. (So that it can determine where the partitions begin and end without metadata.) On the next iteration it can scan until it finds the first two elements out of order, which will be P and one element less than P, and scan until it finds an element greater than P. It then moves P to the end of the chunk, and performs the algorithm on the chunk of data less than P. Other than the temporary relocation of P, this is basically how quicksort works.

Deviation of Algorithm from Quicksort:
Since the algorithm needs the data to be in a series of "chunks" of [partition][data between this partition and the previous partition], we have to format the data down the right side until we find the maximum element to get it into this series of chunks, before the rest of the algorithm can run.

This algorithm is quite strange, and I am terrible at explanations, but as proof of concept, here's the a link to my C++ code with a naive quicksort, my inplace quicksort, and stdsort: http://ideone.com/4iCSo (I acknowledge there's still a lot of optimizing that could be done, and that this algorithm is so slow it is almost completely useless in general) The meat of the question is: is this algorithm still a quicksort?

I'm not clear on the scope of this site, this question might be better suited to https://cs.stackexchange.com/ or https://stackoverflow.com/.

  • $\begingroup$ It wasn't until afterwords that I realized a 64bit quicksort that only recurses on the small side and iterates the large partition will always use less than ~1260 bytes, making it O(1) space overhead in practice if not theory. $\endgroup$ – Mooing Duck May 9 '12 at 17:41
  • 5
    $\begingroup$ Why do you care? If it's a good algorithm, use it. If it's not, don't. Why does it matter what it's called? $\endgroup$ – Jeffε May 9 '12 at 19:08
  • 2
    $\begingroup$ @MooingDuck Tsuyoshi's point is that all the references you list describe an upper bound of log n for space. $\endgroup$ – Suresh Venkat May 10 '12 at 0:39
  • 1
    $\begingroup$ See When are two algorithms said to be “similar”?. $\endgroup$ – Kaveh May 10 '12 at 3:59
  • 4
    $\begingroup$ @PeterShor there is no central authority as far as you know....(insert evil laugh) $\endgroup$ – Suresh Venkat May 10 '12 at 19:03