openbsd/src/lib/libc/stdlib/qsort.c, branch OPENBSD_7_9

Don't fall back to heapsort() if we would otherwise switch to

2017-05-30T14:54:09+00:00

insertion sort (when the number of elements is < 7).

Support swapping 32-bit aligned elements on 64-bit platforms.

2017-05-24T21:18:25+00:00

Previously they would be swapped a byte at a time when sizeof(int) != sizeof(long). Idea from FreeBSD.

Use David Musser's introsort algorithm to fall back to heapsort(3)

2017-05-20T12:48:56+00:00

when the recursion depth reaches 2*lg(n + 1). This avoids quicksort's quadratic behavior for pathological input without appreciably changing the average run time.

The BSD qsort() performs tail recursion elimination on the second

2017-05-17T16:58:20+00:00

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@

Remove unnecessary casts of 'a' to char * since 'a' is already char *.

2017-01-04T15:20:30+00:00

This is a remnant from the original 4.4BSD code that had 'a' as void * in the function args. No binary change. OK bluhm@

Wrap so that calls go direct and the symbols not in the

2015-09-13T08:31:48+00:00

C standard are all weak. Apply __{BEGIN,END}_HIDDEN_DECLS to gdtoa{,imp}.h, hiding the arch-specific __strtorx, __ULtox_D2A, __strtorQ, __ULtoQ_D2A symbols.

Disable the "switch to insertion sort" optimization to avoid quadratic

2014-06-12T14:54:25+00:00

behavior for certain inputs. From NetBSD. OK tedu@

Use size_t in appropriate places; fixes sorting of big arrays;

2010-02-08T11:04:07+00:00

after the diff was written, I made it similar to the freebsd fix of the same code; pr6287 ok millert@ guenther@

zap remaining rcsid.

2005-08-08T08:05:37+00:00

Kill old files that are no longer compiled. okay theo

ansi + de-register

2005-03-30T18:51:49+00:00

ok otto deraadt