Abstract

I improved Quicksort secure and faster in C language.

Pivot hole instead of swaps reduces the number of copies about 1/3, then the simplest new quicksort is faster than the linux library qsort(3). An issue of repeated elements is solved by asymmetric loops and exclusion of continuous equal elements from sub-partitions. Random choice of pivot avoids other malicious input data. Tandomization is limited by the depth of recursion to reduce the cost. The median of several elements make quicksort faster than the simplest new quicksort. Quicksort and indirect Mergesort are complementary to each other, thus a hybrid sort of them is more faster. When N is very small, linear insertion sort is the fastest, thus a hybrid sort of Quicksort and indirect Mergesort and linear Insertion sort (QMI sort) is the fastest in practical element size.

The following chart exhibits relative elapsed time in various number of elements N. Y axis is normalized elapsed time / nlog(n) where the value of quick_hole() at N=2^20 is 1.

qsort_med3 : Conventional quicksort. Pivot is the median of 3 elemnets.
quick_random : New quicksort. Pivot is the median of several elements.
quick_hybrid : Hybrid sort of quicksort and indirect Mergesort.
QMI_sort : QMI sort.
data