Sorting Algorithm Summary
Table of Contents
The following table summarizes common characteristics of popular sorting algorithms, not including string sort algorithms (I may add those later here or write another separate post).
| algorithm | In Place? | Stable? | parallel? | worst | average | best | remarks |
|---|---|---|---|---|---|---|---|
| selection | y | n | n | N2/2 | N2/2 | N2/2 | N exchanges |
| insertion | y | y | n | N2/2 | N2/4 | N | use for small N or partially ordered |
| shell | y | n | n | ? | ? | N | tight code, sub quadratic |
| merge | n* | y | y | NlgN | NlgN | NlgN | NlgN guarantee, stable |
| quick* | y | n | y | N2/2 | 2NlnN | NlgN | probabilistic guarantee, fastest in practice |
| heap | y | n | n | 2NlgN | 2NlgN | NlgN | NlgN guarantee, in place |
| counting | n* | n | y | N+R | N+R | N+R | integer keys, suitable where max-min (R) not >> N, often used as subroutine of radix sort. If sparse, can use hashmap to save space. |
| bucket | n | n | y | N2/2 | N+k | N+k | k denotes number of buckets, needs linked lists, dynamic arrays to hold items in buckets |
| Cartesian | y | n | n | Nlogk | ? | N | k denotes average of number of consecutive pairs, can be viewed as a version of selection and heap sort maintaining a priority queue |
Notes:
- There are in place merge sort algorithms which are a little nontrivial to implement, one way is to do in place merge with bottom up approach. Merge sort on linked lists uses O(1) extra space.
- 3-way quick sort can improve best case running time to O(N) in presence of duplicate keys.
- Counting sort with key indexed counting is stable, uses extra O(N) space for output array. If disregarding the count array, the input array can be used for returning although it is no longer stable.
Implementations in Core Java as of JDK 1.8, DualPivotQuickSort (cut off threshhold of 47 to insertion sort) is used for primitives and a variant of TimSort (a stable, adaptive, iterative merge sort adapted from Tim Peter’s list sort for Python, uses binary insertion sort) is used for objects.