<div class="gmail_quote">On Fri, May 6, 2011 at 18:59, S V N Vishwanathan <span dir="ltr"><<a href="mailto:vishy@stat.purdue.edu">vishy@stat.purdue.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div id=":581">I did a bit more investigation and found that this worst case is<br>
happening when all the elements of the array are the same. I am<br>
detecting this in my code and avoid calling the sort as a stop gap<br>
measure.<br>
<br>
I don't think there will be trouble with a O(n) memory in a queue but a<br>
recursive call overflows the stack.</div></blockquote></div><br><div>The problem is that if you are blowing the stack, then you are seeing quadratic behavior which is not acceptable either. So "putting the stack on the heap" (managing the stack manually) isn't an acceptable solution, the quadratic complexity has to be fixed. I believe that this worst-case behavior is pretty hard to hit with the pivot choice in PetscSortInt_Private, I know it is a problem with the pivot choice in the other variants, they just didn't get updated when PetscSortInt was updated.</div>
<div><br></div><div>Always dynamically allocating memory is not ideal because it costs more on some architectures. Tracking the stack depth and switching to manual management of the stack is about the same amount of programming effort as falling back to heap sort, but the latter guarantees log-linear complexity and no dynamic memory allocation.</div>