- 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 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
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 - min-comparison sorting, min-comparison merging, min-comparison 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 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
- 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() | O() |
O(1) | |
| Cascade merge sort | |||||
Cocktail sort |
O(n) | O() |
O() |
O(1) | (V/D) - Bubble Sort |
Comb sort |
O(n) | Ω() | Ω() | O(1) | (V/D) - Bubble Sort |
Cycle sort |
Θ() | Θ() | Θ() | Θ(n) | Write efficient |
| Gnome sort | O(n) | O() | O() | O(1) | Bubble + Insertion sort |
Heapsort |
Ω(n), O(nlogn) | O(nlogn) | O(nlogn) | O(1) |
Detailed notes |
Insertion sort |
O(n) | O() | O() | O(n) | |
Introsort |
O(nlogn) | O(nlogn) | O(nlogn) | Quick sort + Heap sort IntroSort Paper |
|
Library sort |
O(n) | O(nlogn) | O() | 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() | 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() | O(n) | |
Selection sort |
O() |
O() |
O() |
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() |
O() |
O(1) | |
Timsort |
O(n) | O(nlogn) | O(nlogn) | O(n) | Merge + Insertion sort |
| Online sorting | |||||
| Cycle sort | Θ() | Θ() | Θ() | Θ(n) | |
| Insertion sort | O(n) | O() | O() | O(n) | |
| Library sort | O(n) | O(nlogn) | O() | O(n) | |
| Merge sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | |
| Polyphase merge sort | |||||
| Stable sorting | |||||
| Bubble sort | O(n) | O() | O() | O(1) | |
| Bucket sort | O(n + k) | O() | O(n.k) | ||
| Cascade merge sort | |||||
| Cocktail sort | O(n) | O() | O() | O(1) | |
| Counting sort | |||||
| Gnome sort | O(n) | O() | O() | O(1) | |
| Insertion sort | O(n) | O() | O() | O(n) | |
| Library sort | O(n) | O(nlogn) | O() | O(n) | |
| Merge sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | |
| Odd–even sort | O() | ||||
| Oscillating merge sort | |||||
| Pigeonhole sort | O(N + n) | O(N + n) | |||
| Proxmap sort | O(n) | O() | O(n) | ||
| Radix sort | O(kN) | O(k + N) | |||
| Non-category 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 | |||||