One optimization implemented in the sample code from "Engineering
a Sort Function" that our qsort lacks is storing the partition value
out of line when convenient. Currently, we swap the partition value
into a[0], but this can significantly degrade performance when the
array is sorted in reverse o
On 64-bit systems, when sorting int-sized elements our qsort will
swap elements byte by byte. On 32-bit systems where sizeof(int)
== sizeof(long) this is not an issue.
Adding support for int-sized swaps results in a nice speedup when
sorting ints (like the qsort regress). Another way to look at
On Sat, May 20, 2017 at 10:20:42AM +0200, Otto Moerbeek wrote:
> On Fri, May 19, 2017 at 09:04:30AM -0600, Todd C. Miller wrote:
>
> > On Thu, 18 May 2017 09:58:14 -0600, "Todd C. Miller" wrote:
> >
> > > I believe the best approach is to switch qsort.c to "introsort".
> > > The changes are mini
On Fri, May 19, 2017 at 09:04:30AM -0600, Todd C. Miller wrote:
> On Thu, 18 May 2017 09:58:14 -0600, "Todd C. Miller" wrote:
>
> > I believe the best approach is to switch qsort.c to "introsort".
> > The changes are minimal and the elimination of the O(n^2) worst
> > case is compelling.
>
> I'v
