Most standard libraries include some sort of standard sorting implementation. Usually, either Quicksort or Mergesort is used, as they generally perform very well in most scenarios. However, combining these algorithms with some other secondary algorithm, such as insertion sort, for small lists can offer a sizeable performance gain as the repeated overhead of partitioning arrays or recursive calls is avoided. The threshold at which to switch between these algorithms is often hard-coded by some developer.
This project evaluates various candidate implementations for standard libraries
at many different threshold values. Specifically, qsort() from GNU's libc is
evaluated extensively. Along with this evaluation, this research has found a
new, faster sorting algorithm by intelligently combining Mergesort with sorting
networks and insertion sort.
Refer to the instructions provided for each language in their corresponding
subdirectory within src/.
The following methods are evaluated:
qsort(from the C standard library)std::sort(from the C++ standard library)- Mergesort
- A basic insertion sort.
- A highly optimized insertion sort.
- Shell Sort
- Mergesort w/ basic insertion sort.
- Mergesort w/ optimized insertion sort.
- Mergesort w/ shell sort.
- Mergesort w/ sorting network.
- Mergesort w/ optimized insertion sort & sorting network.
- Quicksort w/ basic insertion sort.
- Quicksort w/ optimized insertion sort.
- A Killer Advisory for Quicksort
- Block Quicksort
- CPython Listsort Explanation
- CPython Listsort Implementation
- General Iterative Quicksort
- Quicksort Basic Overview
- Quicksort is Optimal
- Sedgewick Quicksort
- The Analysis of Quicksort Programs
qsort(glibc)qsort(llvm C++)qsort(musl)std::sort(libc++)std::sort(libstdc++)