Bubble | bad for sorted or reversed input | n 2 ; n 2 | n ; 1 | n or 1 |
Cocktail | little performance improvement over bubble sort | n 2 | n | 1 |
Comb | speeds up when data is nearly sorted | n 2 | nlogn | 1 |
Gnome | simple and slow, works with one item at a time | n 2 | n | 1 |
Heap | independent of data distribution | nlogn | nlogn or n | n or 1 |
Weak Heap | independent of data distribution, decreased amount of comparisons | nlogn | nlogn or n | n or 1 |
N-Heap | independent of data distribution, should be faster than default heap. n = 3 | nlogn | nlogn or n | n or 1 |
Bottom-up Heap | upgraded version of heapsort with decreased number of comparisons | nlogn | nlogn or n | n or 1 |
Insertion | simple, but less effective than quicksort, heapsort or merge sort | n 2 ; n 2 | n ; 1 | n or 1 |
Merge | independent of data distribution | nlogn | nlogn | n |
Odd-even | presented to be effective on processors with local interconnections | n 2 | n | 1 |
Odd-even (Batcher) | more efficient version of odd-even sort | nlogn 2 | logn 2 | logn 2 |
Quick | bad for sorted or reversed input | n 2 | nlog 2n | n or logn |
Quick dual | enchanced version of quicksort | n 2 | 2nlnn | n or logn |
Ksort | modified version of quicksort, faster than heap at less than 7 million elements | n 2 | nlog 2n | n or logn |
Selection | the least number of swaps among all the algorithms | n 2 ; n | n 2 ; 1 | 1 |
Double selection | modified version of selection sort with more workload, but better efficiency | n 2 ; n | n 2 ; 1 | more than Selection |
Shellsort | it is optimization of insertion sort | n 3/2 or nlogn 2 | nlogn | 1 |
Slow | it's slow, who would ever need it? | | | |
Smooth | variant of heapsort, good for nearly sorted data | nlogn | n | n or 1 |
Stooge | it's a bit faster than slow sort | n 2.7095 | | n |