quicksort的Linux实现是否“回退"了?插入排序? [英] Does the Linux implementation of quicksort "back off" to insertion sort?

问题描述

我在Bentley& McIlroy(1993)提出，当数组变得足够小时，他们建议的Quicksort实现使用插入排序.

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

我很想知道现代内核是否使用相同的方法.有谁知道例如Linux内核是否以这种方式从Quicksort切换到Insertion Sort?

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?

推荐答案

假设您的意思是C库中的qsort，以下是最新glibc中的qsort()，它是大多数Linux系统中使用的glibc: http://www.cs.umaine.edu/~chaw/200801/capstone/n/qsort.c.html .

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.

对于小分区，确实可以切换到插入.尽管经验选择的数字可能需要更新，但碰巧使用了4个元素作为阈值.

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

这篇关于quicksort的Linux实现是否“回退"了?插入排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！