§ 2.1 Elementary Sorts.
Algorithms and Data Structures Cheatsheet
The Analysis of Heapsort paper
| Name | Princeton java link | .Net impl. | Misc |
|---|---|---|---|
| BinaryInsertion | BinaryInsertion.java | BinaryInsertion.cs | BinaryInsertion<T> where T : IComparable<T> |
| Heap | Heap.java | Heap.cs | heapsort, not the data structure |
| Insertion | Insertion.java | Insertion.cs | |
| InsertionPedantic | InsertionPedantic.java | InsertionT.cs | Insertion<T> |
| InsertionX | InsertionX.java | InsertionX.cs | optimized version of insertion sort that uses half exchanges to reduce data movement.. |
| Merge | Merge.java | Merge.cs | mergesort |
| MergeBU | MergeBU.java | MergeBU.cs | BOTTOM-UP MERGESORT |
| MergeX | MergeX.java | MergeX.cs | optimized merge sort MergeX<T> where T : IComparable<T> |
| Quick | Quick.java | Quick.cs | |
| Quick3Way | Quick3way.java | Quick3Way.cs | |
| QuickX | QuickX.java | QuickX.cs | |
| Selection | Selection.java | Selection.cs | |
| Shell | Shell.java | Shell.cs |
| ... | inplace? | stable? | best | average | worst | remarks |
|---|---|---|---|---|---|---|
| selection | Y | N | n^2/2 | n^2/2 | n^2/2 | n exchanges |
| insertion | Y | Y | n |
n^2/4 | n^2/2 | use for small n, or partially ordered |
| shell | Y | N | nlog3n | ? | cn^3/2 | tight code; subquadratic |
| merge | N | Y | nlogn/2 | nlgn | nlgn | n*log(n) guarantee, stable |
| timsort | N | Y | n | nlgn | nlgn | improves mergesort when preexisting order |
| quick | Y | N | nlgn | 2nlnn | ½n^2 | n*log(n) probabilistic guarantee, fastest in practice |
| 3-way quick | Y | N | n |
2nlnn | ½n^2 | improves quicksort when duplicate keys |
| heap | Y | N | 3n | 2nlgn | 2nlgn | n*log(n) guarantee, in place, best n if keys distinct? |
| not yet | Y | Y | n |
nlgn | nlgn | holy sorting grail |