4 ms·

> Another one of my common things I do at work is replacing quicksort implemented using recursion with an iterative version so that the stack doesn't keep getti

• alexkus 14y ago
  The usual suspects are recursive qsort() implementations inside libc on Solaris, HP-UX and AIX. They've got a lot better in the latest releases but our software is supported on the older platforms (as far back as Solaris 7 for example) so it has to be made to work on them. glibc has done it properly for years. So this is mainly software written in C/C++. Other languages do sorting in one of several ways:- 1) Just wrapper libc's qsort() and so suffer the same problem if that's susceptible. 2) Implement the naive recursive stack-gobbling quicksort in their own language as a module/package/import/library. 3) Implement their own sorting algorithm that avoids lots of recursive calls or does the tricks to pick suitable pivots, etc. It's #1 and #2 that tend to suffer from problems when sorting large datasets, or the pathalogical cases that pinpoint the absolute worst in the design of the algorithm.
  • irahul 14y ago
    > The usual suspects are recursive qsort() implementations inside libc on Solaris, HP-UX and AIX. Oh, I am mainly familiar with GNU C library. Wasn't aware others were shipping recursive qsort implementation, especially considering that a non recursive qsort is an undergrad level exercise.