# Sorting

## sorting algorithm

A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:

### Dictionary of algorithms

Dictionary of algorithms

### Sorting Visualization

Sorting Visualization

### Sorting Wiki Summary

Sorting Wiki Summary

Sorting algorithms can be divided into categories

### Sorting algorithms

1. Comparisons based sorts - 24 algorithms in this category
2. Online sorts - 5 algorithms in this category
3. Stable sorts - 14 algorithms in this category

Donald Knuth pioneer in algorithms and field of Computer Science have divided sorting into

1. Internal sorting - by insertion, by exchange, by selection, by merging, by distribution
2. Optimum sorting - min-comparison sorting, min-comparison merging, min-comparison selection
3. External sorting

### Comparisons based sorting

It is particular type of sorting algorithm which read the list elements through comparison operator that determines which of two elements should occur first int he final sorted list.

Algorithms

*(S) - Stable sorts

### Online sorts

These sorts can start sorting their input without having received all of it. It can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.

Algorithms

*(S) - Stable sorts

### Stable sorts

A sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

Algorithms

### Time complexity chart

GoodFairPoor

*(V/D) - Variant or derived from

AlgorithmTime complexitySpace complexityNotes
BestAverageWorst
Bogosort Ω(n) O(n × n!) Unbounded O(n)
Bubble sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(1)
Cocktail sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(1) (V/D) - Bubble Sort
Comb sort O(n) Ω($\frac{{n}^{2}}{{2}^{p}}$) Ω(${n}^{2}$) O(1) (V/D) - Bubble Sort
Cycle sort Θ(${n}^{2}$) Θ(${n}^{2}$) Θ(${n}^{2}$) Θ(n) Write efficient
Gnome sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(1) Bubble + Insertion sort
Heapsort Ω(n), O(nlogn) O(nlogn) O(nlogn) O(1) Detailed notes
Insertion sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(n)
Introsort O(nlogn) O(nlogn) O(nlogn) Quick sort + Heap sort
IntroSort Paper
Library sort O(n) O(nlogn) O(${n}^{2}$) O(n) (V/D) - Insertion sort
Merge sort O(n), O(nlogn) O(nlogn) O(nlogn) O(n) Detailed notes
Odd–even sort O(n) O(${n}^{2}$) O(1) *(V/D) - Bubble sort
Oscillating merge sort
Patience sorting O(nlogn) O(n) Longest common sequence
Polyphase merge sort
Quicksort O(nlogn) O(nlogn) O(${n}^{2}$) O(n)
Selection sort O(${n}^{2}$) O(${n}^{2}$) O(${n}^{2}$) O(n)
Shellsort Depends on gap seq Depends on gap seq Depends on gap seq O(n) Faster on partial sorted list
Smoothsort O(n) O(nlogn) O(nlogn) O(n) *(V/D) - Heap sort
Stooge sort O(n) Slower than bubble sort
Strand sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(1)
Timsort O(n) O(nlogn) O(nlogn) O(n) Merge + Insertion sort
Online sorting
Cycle sort Θ(${n}^{2}$) Θ(${n}^{2}$) Θ(${n}^{2}$) Θ(n)
Insertion sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(n)
Library sort O(n) O(nlogn) O(${n}^{2}$) O(n)
Merge sort O(nlogn) O(nlogn) O(nlogn) O(n)
Polyphase merge sort
Stable sorting
Bubble sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(1)
Bucket sort O(n + k) O(${n}^{2}$) O(n.k)
Cocktail sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(1)
Counting sort
Gnome sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(1)
Insertion sort O(n) O(${n}^{2}$) O(${n}^{2}$) O(n)
Library sort O(n) O(nlogn) O(${n}^{2}$) O(n)
Merge sort O(nlogn) O(nlogn) O(nlogn) O(n)
Odd–even sort O(${n}^{2}$)
Oscillating merge sort
Pigeonhole sort O(N + n) O(N + n)
Proxmap sort O(n) O(${n}^{2}$) O(n)
Radix sort O(kN) O(k + N)
Non-category Sorts
American flag sort
Burstsort
Cartesian tree
Comparison sort
Dutch national flag problem
Elevator algorithm
External sorting
Flashsort
Integer sorting
Internal sort
J sort
Median cut
Ordicate
Pairwise sorting network
Pancake sorting
Partial sorting
Proxmap sort
Quantum sort
Samplesort
Sorting network
Spaghetti sort