On 10/8/2011 1:56 PM, Andrei Alexandrescu wrote:
On 10/8/11 12:30 PM, Xinok wrote:
I didn't mean for this text to be anything official. I just felt it was
important to provide an explanation of my algorithm so others could
better understand my algorithm and it's implications. That's all.
There's also the issue of, "what if I'm not the first?" I couldn't find
anything similar to the "range swap", but that doesn't mean it didn't
already exist.
Writing papers isn't my forte, I'm a self taught programmer. So if my
algorithm ever gains popularity, I'll let the experts deal with it.
My attempt was to make a few suggestions that would improve your
writeup, which in turn not only helps popularity of the algorithm, but
also you to hone a useful skill.
Thanks for that. :) I can't update the original link, so the text is
what it is. I'll look into making a better write-up of my algorithm and
posting it somewhere more permanent.
Also there are a few oddities in the text:
* "- Constant additional memory (one memory allocation per thread)" ->
the parenthesis does not sustain the point. There could be one memory
allocation but it might allocate a non-constant amount.
I thought it was important to clarify that. My algorithm is easy to
parallelize, but it does require allocating a unique block of memory for
each thread. It is relatively constant as well, as it would make sense
that the number of running threads matches the number of cores in the
hardware. The only reason to allocate a non-constant amount is if you
include the optimization I mentioned, to allocate O(n/1024) space.
Then you may want to say:
* Constant additional memory and one call to an allocation routine per
thread.
I'll do that.
I think it's an issue worth addressing though. Some programmers might
assume that, because it's a variant of merge sort, stack overflows won't
be an issue. When I originally implemented my algorithm, I didn't use
tail calls and I had problems with stack overflows on partially sorted
data. So it is an issue.
No, it's not. Please think through: tail recursion IS A loop, period.
(BTW I see you use simple tail recursion as opposed to the more general
tail calls.) It's cut and dried. So no discussion is needed. Just
mention there is no risk of stack overflow, without ever mentioning tail
calls. In fact there's not even a need to mention that because otherwise
the algorithm would have non-constant space complexity, which you
clarify it doesn't.
Take a look at the Wikipedia page for quick sort. It mentions issues
with the algorithm, such as using the first element as the pivot causes
worst-case behavior on sorted data, and even something I didn't know
about is integer overflow when choosing a pivot. It also mentions tail
calls / tail recursion five times.
https://secure.wikimedia.org/wikipedia/en/wiki/Quick_sort#Implementation_issues
I'll reduce talk about tail calls, I'll probably just list it under
optimizations, but I'm not removing it completely. Otherwise, I'll make
a note that, depending on the implementation, the range swap can result
in a stack overflow, but I won't mention tail calls / tail recursion as
a solution.
