 Dictionary of algorithms
 Sorting Visualization
 Sorting Wiki Summary
 Sorting algorithms
 Comparisons based sorting
 Online sorts
 Stable sorts
 Time complexity chart
This article talks about Sorting, Sorting techniques/algorithms in computer science
Let’s start with Wikipedia entry about sorting
sorting algorithm
A sorting algorithm is an algorithm that puts elements of a list in a certain order. The mostused 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 humanreadable output. More formally, the output must satisfy two conditions:
Dictionary of algorithms
Sorting Visualization
Sorting Wiki Summary
Sorting algorithms can be divided into categories
Sorting algorithms
 Comparisons based sorts  24 algorithms in this category
 Online sorts  5 algorithms in this category
 Stable sorts  14 algorithms in this category
Donald Knuth pioneer in algorithms and field of Computer Science have divided sorting into
 Internal sorting  by insertion, by exchange, by selection, by merging, by distribution
 Optimum sorting  mincomparison sorting, mincomparison merging, mincomparison selection
 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
 Adaptive heap sort
 Bogosort
 Bubble sort  (S)
 Cascade merge sort  (S)
 Cocktail sort  (S)
 Comb sort
 Cycle sort
 Gnome sort  (S)
 Heapsort
 Insertion sort  (S)
 Introsort
 Library sort  (S)
 Merge sort  (S)
 Odd–even sort  (S)
 Oscillating merge sort  (S)
 Patience sorting
 Polyphase merge sort
 Quicksort
 Selection sort
 Shellsort
 Smoothsort
 Stooge sort
 Strand sort
 Timsort
*(S)  Stable sorts
Online sorts
These sorts can start sorting their input without having received all of it. It can process its input piecebypiece 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
 Cycle sort
 Insertion sort  (S)
 Library sort  (S)
 Merge sort  (S)
 Polyphase merge sort
*(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
 Bubble sort
 Bucket sort
 Cascade merge sort
 Cocktail sort
 Counting sort
 Gnome sort
 Insertion sort
 Library sort
 Merge sort
 Odd–even sort
 Oscillating merge sort
 Pigeonhole sort
 Proxmap sort
 Radix sort
Time complexity chart
Good  Fair  Poor 

^{*}(V/D)  Variant or derived from
Algorithm  Time complexity  Space complexity  Notes  

Best  Average  Worst  
Adaptive heap sort  
Bogosort 
Ω(n) 
O(n × n!)  Unbounded 
O(n)  
Bubble sort 
O(n)  O(${n}^{2}$)  O(${n}^{2}$) 
O(1)  
Cascade merge sort  
Cocktail sort 
O(n)  O(${n}^{2}$) 
O(${n}^{2}$) 
O(1)  (V/D)  Bubble Sort 
Comb sort 
O(n)  Ω($\frac{{n}^{2}}{{2}^{\mathrm{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)  
Cascade merge sort  
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)  
Noncategory Sorts  
Adaptive sort  
American flag sort  
Bead 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  
Spreadsort  
Topological sorting  
Tournament sort  
Tree sort  
UnShuffle sort 