Sorting is the most fundamental problem in computer science. The followings are the most prominent sorting algorithms.
| Name |
Type |
Time Complexity |
Best Running Time |
Memory |
Stable* | Notes |
| Heapsort |
Comparison |
O(n log n) |
O(n log n) |
O(1)
|
No | |
| Merge sort |
Comparison |
O(n log n) |
O(n log n) |
O(n) |
Yes | |
| Quicksort |
Comparison |
O(n2) |
O(n log n)
|
O(log n) |
No | When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. |
| Insertion sort |
Comparison |
O(n2)
|
O(n) |
O(1) |
Yes | |
| Bubble sort | Comparison
| O(n2)
| O(n) | O(1) | Yes | |
| Counting sort |
Non-comparison |
O(n) |
O(n) |
O(n) |
Yes | Assumes the input numbers are in the set {1,2...,k}. Linear time is achieved if k = O(n)
|
| Radix sort |
Non-comparison |
O(n) |
O(n) |
O(n) |
Yes | Assumes the input
numbers are in the set {1,2...,k} and and each number has d
digits. Linear time is achieved if both d and k are O(n) |
| Bucket sort |
Non-comparison |
O(n2) |
O(n) |
O(n) |
Yes | Requires knowledge of the probabilistic distribution of the input |
| External sort | | | | | | |
*A sorting algorithm is not stable if the duplicate elements' order is changed during the sort | 