On 11/10/2014 04:54 PM, Steven Ross wrote:
I did an algorithm search in 2008 when preparing the boost submission. ALR came out, fairly similar to my paper. I have not seen much attention paid in academia to hybrid radix sorting.
Okay, so assuming a third party were to implement a sorting algorithm for Boost. Why they would choose your paper over the 2008 paper?
I'm worried about "similar" and "adaptation" above. If I see that function whatever_sort implements an algorithm from paper N, with 200 citations, then I can assume enough people reviewed the algorithm. If that function implements an adaptation, then I'm not really sure what complexity I can expect. Since you've read the overview, how about just looking through the code and seeing if it works as described, or testing it? Can you ever be sure a concrete implementation correctly applies an abstract concept without looking at the implementation? These implementations are fast for the same reason ALR and AFS are. They have superior worst-case performance because they fall back to std::sort at a size that optimizes worst-case performance. The only other difference is that these algorithms scan to see if they can shrink the range each iteration, which improves performance for non-worst-case distributions with little impact on worst-case distributions.
Which "these algorithms"? ALR and AFS? If so, it would mean they are better? -- Vladimir Prus CodeSourcery / Mentor Embedded http://vladimirprus.com