Does the Linux implementation of quicksort "back off" to insertion sort?

Question

I was reading in Bentley & McIlroy (1993) that their suggested implementation of Quicksort uses Insertion Sort when the arrays get small enough.

I was curious to know whether modern-day kernels use this same maneuver. Does anyone know whether the Linux kernel, for instance, switches from Quicksort to Insertion Sort in this way?

Answer 1

Assuming you mean the qsort from the C library, here's the qsort() from a somewhat recent glibc, which is the one used in most Linux systems: http://www.cs.umaine.edu/~chaw/200801/capstone/n/qsort.c.html.

It does indeed switch to insertion for small partitions. It happens to use 4 elements for the threshold, though it's possible the empirically-selected number needs updating.

/* Discontinue quicksort algorithm when partition gets below this size.
   This particular magic number was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4

Answer 2

If you're referring to the qsort from the Linux standard C library (GLIBC), that's actually implemented as merge sort, not quick sort. It will only fall back to an in-place quick sort if it's unable to allocate enough memory for merge sort.

Don't believe me? Check out the source code for qsort() in GLIBC here: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/msort.c;hb=HEAD#l306

Mats Linander has a great article summarizing the various implementations for qsort() in different standard C libraries here: http://calmerthanyouare.org/2013/05/31/qsort-shootout.html (hint: most don't actually use quick sort!)