快速排序的Linux实现是否“后退”到插入排序?

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

我在Bentley & McIlroy(1993)中读到，当数组足够小时，他们建议的Quicksort实现使用插入排序。

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?

我很想知道现代的内核是否也使用同样的手法。有人知道Linux内核是否以这种方式从快速排序切换到插入排序吗?

2 个解决方案

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

假设您指的是来自C库的qsort，这里是来自最近的glibc的qsort()，这是在大多数Linux系统中使用的一个: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.

对于小的分区，它确实切换到插入。它碰巧使用了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

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

如果您指的是来自Linux标准C库(GLIBC)的qsort，那么它实际上实现为merge sort，而不是quick 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

不相信我吗?在GLIBC中查看qsort()的源代码:http://sourceware.org/git/?

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!)

Mats Linander撰写了一篇很棒的文章，总结了不同标准C库中qsort()的各种实现:http://calmerthanyouare.org/2013/05/31/qsortshootout .html(提示:大多数实际上不使用快速排序!)

#1