Sorting - Comparison
Jump to navigation
Jump to search
Problem Description
A sorting algorithm is an algorithm that puts elements of a list in a certain order. A Comparison sort compares actual values of the items. The best time complexity that can be reached in comparison based sorting is nlogn.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | Naive sorting (1940) | |
| Selection Sort (1962) | ||
| Bubble Sort (1956) | ||
| Shell Sort; (Shell 1959) (1959) | ||
| Shell Sort; (Frank & Lazarus 1960) (1960) | ||
| Shell Sort; (Pratt 1971) (1971) | ||
| Shell Sort; (Sedgewick; 1986) (1986) | ||
| Odd Even Sort Parallel Implementation (1972) | ||
| nlogn | Merge Sort (1945) | |
| Tree sort (1962) | ||
| Quick Sort (1961) | ||
| Intro Sort (1997) | ||
| Cube Sort Parallel Implementation (1992) | ||
| Heap Sort (1964) | ||
| Linear | Counting Sort (1954) | |
| Tim Sort (2002) | ||
| Flash Sort (1998) | ||
| Bucket Sort (1940) | ||
| Bitonic Merge Sort Parallel Implementation (1968) | ||
| Bead Sort (2002) | ||
| Burst Sort (2004) | ||
| Radix Sort (1940) | ||
| Thorup's Sorting Algorithm (2002) | ||
| Spreadsort (2002) | ||
| Spaghetti Sort Parallel Implementation (1984) | ||
| logn |