Я читал в Bentley & McIlroy (1993), что предложенная ими реализация быстрой сортировки использует сортировку вставками, когда массивы становятся достаточно маленькими.
Мне было любопытно узнать, используют ли современные ядра тот же маневр. Кто-нибудь знает, переключается ли ядро Linux, например, с быстрой сортировки на сортировку вставками таким образом?
Предполагая, что вы имеете в виду qsort из библиотеки C, вот qsort() из несколько недавней glibc, которая используется в большинстве систем 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
Если вы имеете в виду qsort из стандартной библиотеки Linux C (GLIBC), то на самом деле она реализована как сортировка слиянием, а не быстрая сортировка. Он вернется к быстрой сортировке на месте, только если не сможет выделить достаточно памяти для сортировки слиянием.
Не верите мне? Ознакомьтесь с исходным кодом qsort() в GLIBC здесь: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/msort.c;hb=HEAD#l306.
У Матса Линандера есть отличная статья, в которой обобщаются различные реализации qsort() в различных стандартных библиотеках C: http://calmerthanyouare.org/2013/05/31/qsort-shootout.html (подсказка: в большинстве случаев быстрая сортировка не используется!)
qsort()в стандартной библиотеке C (не в ядре), хотя имя, вероятно, произошло от Quicksort, в стандарте нет требования о том, как она реализована. (Это не отвечает на ваш вопрос, поэтому это комментарий.) - person Keith Thompson schedule 01.10.2013