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

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

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