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.
