> 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.
I did a bit more investigation and found that this worst case is happening when all the elements of the array are the same. I am detecting this in my code and avoid calling the sort as a stop gap measure. I don't think there will be trouble with a O(n) memory in a queue but a recursive call overflows the stack. vishy