Sorting - Comparison

From Algorithm Wiki
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

SortingBoundsChart.png

Step Chart

SortingStepChart.png

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