Data structures and algorithms cheat sheet, sorting algorithms quick reference, comparison of sorting algorithms on auxiliary space used, sorting algorithms cheat sheet, stable vs inplace vs comparison sorting algorithms quick reference
Sorting algorithms  A comparison
Algorithm 
Time complexity 
Space complexity 
Inplace 
Stable 
Comparison 
No. of comparisons 

Best 
Average 
Worst 
Total 
Auxiliary 
Min 
Max 

Bubble sort 
O(n) 
O(n^{2}) 
O(n^{2}) 
O(n) 
O(1) 
Yes 
Yes 
Yes 
n(n1)/2 
n(n1)/2 
O(n^{2}) 
O(n^{2}) 
O(n^{2}) 
O(n) 
O(1) 
Yes 
No 
Yes 
n(n1)/2 
n(n1)/2 

Insertion sort 
O(n) 
O(n^{2}) 
O(n^{2}) 
O(n) 
O(1) 
Yes 
Yes 
Yes 
n1 
n(n1)/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(n^{2}) 
O(n) 
O(1) 
Yes 
No 
Yes 
n*log_{2}n 
n(n1)/2 
Heap sort 
O(n log n) 
O(n log n) 
O(n log n) 
O(n) 
O(1) 
Yes 
No 
Yes 
n*log_{2}n 
n*log_{2}n 
Bucket sort 
O(n+k) 
O(n+k) 
O(n^{2}) 
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 log^{2}n) 
O(n log^{2}n) 
O(n) 
O(1) 
Yes 
No 
Yes 
n*log_{2}n 

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.
Inplace sorting algorithm
A sorting algorithm is inplace 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
No comments:
Post a Comment