<div class="gmail_quote">On Fri, May 6, 2011 at 07:37, 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=":263">I am using PetscSortRealWithPermutation to sort an array with around<br>
200K elements and it causes a segfault.<br>
<br>
STL sort is able to handle this array without any problems.<br>
<br>
I looked at the gdb backtrace. It primarily seems to be because the<br>
stack is exhausted because of recursive calls to<br>
PetscSortRealWithPermutation_Private. I am wondering if it might not be<br>
a better idea to implement PetscSortRealWithPermutation_Private without<br>
recursion to avoid these errors?</div></blockquote></div><br><div>Non-recursive may still need O(n) memory because a "stack" needs to be stored, and it just masks the real problem which is decay to quadratic behavior.</div>
<div><br></div><div>This issue of hitting worst case of quicksort came up before with PetscSortInt. It would be interesting to know if the pivot selection in PetscSortInt_Private would fix the worst-case behavior that you see? If so, then the same changes could be made to the other sorting routines.</div>
<div><br></div><div>Better solutions involve putting real work into finding good pivots or falling back to heap sort ("introsort") when bad behavior is detected.</div>