我在 Bentley & McIlroy (1993) 中读到，当数组变得足够小时，他们建议的快速排序实现使用插入排序。
我很想知道现代内核是否使用同样的策略。有谁知道Linux内核是否以这种方式从快速排序切换到插入排序？
最佳答案
假设您指的是 C 库中的 qsort，这是来自最近的 glibc 的 qsort()，它是大多数 Linux 系统中使用的:http://www.cs.umaine.edu/~chaw/200801/capstone/n/qsort.c.html .
它确实切换到小分区的插入。它碰巧使用 4 个元素作为阈值，尽管根据经验选择的数字可能需要更新。
/* 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
关于linux - Linux中的快速排序 "back off"是否实现为插入排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19123683/