> Todd C. Miller wrote on Wed, May 17, 2017 at 10:58:20AM -0600: > > > CVSROOT: /cvs > > Module name: src > > Changes by: [email protected] 2017/05/17 10:58:20 > > > > Modified files: > > lib/libc/stdlib: qsort.c > > > > Log message: > > The BSD qsort() performs tail recursion elimination on the second > > side of the array being partitioned to save on stack space. Greater > > savings can be gained by choosing recursion for the smaller side > > of the partition and eliminating recursion for the larger side. > > This also results in a small but measurable performance gain. > > OK otto@ schwarze@ > > For the record, this commit changes worst-case stack space requirements > from O(n) to O(log n). The following are unchanged: > > - average stack space: O(log n) > - average run time: O(n log n) > - worst case run time: O(n^2) > > The latter is "ouch", but unavoidable for Quicksort-based algos.
Note that "worst case stack use" could potentially be newly allocated stack growth which is zero fault, so the win can be big.
