Data structures and algorithms cheat sheet, sorting algorithms quick reference, comparison of sorting algorithms on auxiliary space used, sorting algorithms cheat sheet, stable vs in-place vs comparison sorting algorithms quick reference
Sorting algorithms - A comparison
|
Algorithm |
Time complexity |
Space complexity |
In-place |
Stable |
Comparison |
No. of comparisons |
||||
|
Best |
Average |
Worst |
Total |
Auxiliary |
Min |
Max |
||||
|
Bubble sort |
O(n) |
O(n2) |
O(n2) |
O(n) |
O(1) |
Yes |
Yes |
Yes |
n(n-1)/2 |
n(n-1)/2 |
|
O(n2) |
O(n2) |
O(n2) |
O(n) |
O(1) |
Yes |
No |
Yes |
n(n-1)/2 |
n(n-1)/2 |
|
|
Insertion sort |
O(n) |
O(n2) |
O(n2) |
O(n) |
O(1) |
Yes |
Yes |
Yes |
n-1 |
n(n-1)/2 |
|
Merge sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
O(n) |
No |
Yes |
Yes |
n*log 2 n |
n*log 2 n |
|
Quick sort |
O(n log n) |
O(n log n) |
O(n2) |
O(n) |
O(1) |
Yes |
No |
Yes |
n*log2n |
n(n-1)/2 |
|
Heap sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
O(1) |
Yes |
No |
Yes |
n*log2n |
n*log2n |
|
Bucket sort |
O(n+k) |
O(n+k) |
O(n2) |
O(n+k) |
|
No |
Yes |
No |
Depends on the algorithm used to sort the elements in each bucket |
|
|
Radix sort |
O(nk) |
O(nk) |
O(nk) |
O(n+k) |
|
Yes |
Yes |
No |
NA |
|
|
Shell sort |
O(n log n) |
O(n log2n) |
O(n log2n) |
O(n) |
O(1) |
Yes |
No |
Yes |
n*log2n |
|
Notations used
- n refers to number of elements to be sorted.
- k in Bucket sort refers to number of buckets, in Radix sort refers to the maximum length of the input elements.
Auxiliary Space
is the temporary space allocated by your algorithm to solve the problem, with respect to input size.
Space Complexity
is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity includes input size.
In-place sorting algorithm
A sorting algorithm is in-place if it requires only O(1) extra space to sort the array.
Stable sorting algorithm
We say that a sorting algorithm is stable if, when two records have the same key, they stay in their original order. A sort is stable if two elements with the same value maintain their same relative order before and after the sort is performed.
Comparison sorting algorithm
Any sort algorithm using comparisons between keys (elements), and nothing else about the keys, to arrange items in a predetermined order (ascending or descending). The predetermined sorted order is determined by a sequence of comparisons between pairs of elements.********************
Related links