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?

## Advertisement

## 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