This library contains implementations of various different sorting algorithms.
The full list of implemented sorting algorithms can be found below.
This library provides extension methods for sorting elements in a sequence. The syntax uses similar syntax to LINQ.
In order to sort the the following collection you can use two different methods.
var x = new int[] { 5, 3, 1, 2, 4 };Method 1: Using a type parameter.
x.Order<int, QuickSort<int>>();
Method 2: Using an instance of the sorting algorithm.
x.Order(new QuickSort<int>());
Both of these methods are implemented for Order, OrderBy, OrderDescending, and OrderDescending and their
overloads and return an IOrderedEnumerable<T> such that sorting algorithms, that support sorting by multiple keys,
can use ThenBy to perform subsequent ordering of elements.
// First orders by parity then by ascending order
x.OrderBy(x => x % 2, new QuickSort<int>()).ThenBy(x => x);
| Name |
Best |
Average |
Worst |
| Batcher Odd-Even Merge Sort |
$\mathcal O(\log^2 n)$ |
$\mathcal O(\log^2 n)$ |
$\mathcal O(\log^2 n)$ |
| Bitonic Sort |
$\mathcal O(\log^2 n)$ |
$\mathcal O(\log^2 n)$ |
$\mathcal O(\log^2 n)$ |
| Parallel Merge Sort |
$\mathcal O(\log^3 n)$ |
$\mathcal O(\log^3 n)$ |
$\mathcal O(\log^3 n)$ |
| Parallel Quicksort
|
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n^2)$ |
| Name |
Best |
Average |
Worst |
| American Flag Sort |
$-$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
| Bucket Sort |
$-$ |
$\mathcal O(n + r)$ |
$\mathcal O(n + r)$ |
| Burstsort |
$-$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
| Counting Sort |
$-$ |
$\mathcal O(n + r)$ |
$\mathcal O(n + r)$ |
| Flashsort |
$\mathcal O(n)$ |
$\mathcal O(n + r)$ |
$\mathcal O(n + r)$ |
| LSD Radix Sort |
$\mathcal O(n)$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
| MSD Radix Sort |
$-$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
$\mathcal O(n\cdot\frac{k}{d})$ |
| Pigeonhole Sort |
$-$ |
$\mathcal O(n + 2^k)$ |
$\mathcal O(n + 2^k)$ |
| Proxmap Sort |
$\mathcal O(n)$ |
$\mathcal O(n)$ |
$\mathcal O(n^2)$ |
| Name |
Best |
Average |
Worst |
| Bubble Sort |
$\mathcal O(n)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Cocktail Shaker Sort |
$\mathcal O(n)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Comb Sort |
$\mathcal O(n\log n)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Dual-Pivot Quicksort |
$\mathcal O(\log n)$ |
$\mathcal O(\log n)$ |
$\mathcal O(n^2)$ |
| Exchange Sort |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Gnome Sort |
$\mathcal O(n)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Odd-even Sort |
$\mathcal O(n)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Quicksort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n^2)$ |
| Name |
Best |
Average |
Worst |
| Introsort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Multi-key Quicksort |
$-$ |
$-$ |
$-$ |
| Timsort |
$\mathcal O(n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Name |
Best |
Average |
Worst |
| B-Tree Sort |
$-$ |
$-$ |
$\mathcal O(n\log n)$ |
| Cartesian Tree Sort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n^2)$ |
| Insertion Sort |
$\mathcal O(n)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Patience Sort |
$\mathcal O(n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Red-Black Tree Sort |
$-$ |
$-$ |
$\mathcal O(n\log n)$ |
| Shellsort |
$\mathcal O(n\log n)$ |
$\mathcal O(n^\frac{4}{3})$ |
$\mathcal O(n^\frac{3}{2})$ |
| Splaysort |
$\mathcal O(n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Tree Sort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Name |
Best |
Average |
Worst |
| Merge Sort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Strand Sort |
$\mathcal O(n)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Name |
Best |
Average |
Worst |
| Binomial Heapsort |
$-$ |
$-$ |
$\mathcal O(n\log n)$ |
| Circle Sort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log^2 n)$ |
| Cycle Sort |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| D-Heap Sort |
$\mathcal O(n\log_dn)$ |
$\mathcal O(n\log_dn)$ |
$\mathcal O(n\log_dn)$ |
| Heapsort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Leftist Heapsort |
$-$ |
$-$ |
$\mathcal O(n\log n)$ |
| Selection Sort |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Smoothsort |
$\mathcal O(n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Tournament Sort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Weak-Heap Sort |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
$\mathcal O(n\log n)$ |
| Name |
Best |
Average |
Worst |
| Pancake Sort |
$\mathcal O(1)$ |
$\mathcal O(n)$ |
$\mathcal O(n)$ |
| Name |
Best |
Average |
Worst |
| Assumption Sort |
$\mathcal O(1)$ |
$\mathcal O(1)$ |
$\mathcal O(1)$ |
| Bogobogosort |
$-$ |
$-$ |
$\mathcal O(n!^{n-k})$ |
| Bogosort |
$\Omega(n)$ |
$\mathcal O(n\cdot n!)$ |
$\mathcal O(\infty)$ |
| Bozosort |
$\mathcal O(n)$ |
$\mathcal O(n!)$ |
$\mathcal O(\infty)$ |
| I Can't Believe It Can Sort |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
$\mathcal O(n^2)$ |
| Permutation Sort |
$\mathcal O(n)$ |
$\mathcal O(n!)$ |
$\mathcal O(n!)$ |
| Quantum Bogosort |
$\mathcal O(n)$ |
The universe is destroyed |
The universe is destroyed |
| Sleep Sort |
$\mathcal O(n)$ |
$\mathcal O(n)$ |
$\mathcal O(n)$ |
| Slowsort |
$\Omega(n^{\log n})$ |
$\Omega(n^{\log n})$ |
$\Omega(n^{\log n})$ |
| Stalin Sort |
$\mathcal O(n)$ |
$\mathcal O(n)$ |
$\mathcal O(n)$ |
| Stooge Sort |
$\mathcal O(n^\frac{\log 3}{\log 1.5})$ |
$\mathcal O(n^\frac{\log 3}{\log 1.5})$ |
$\mathcal O(n^\frac{\log 3}{\log 1.5})$ |