Sort
An algorithm that puts values from an ordered data structure into a desired order. It may use a comparator to customize the ordering logic.
Common Sorts
| Sort | Time (Best) | Time (Average) | Time (Worst) | Space (Worst) | Sort Stability? |
|---|---|---|---|---|---|
| Bubble Sort | O(N) |
O(N^2) |
O(N^2) |
O(1) |
yes |
| Quicksort | O(NlogN) |
O(NlogN) |
O(N^2) |
O(logN) |
no |
| Merge Sort | O(NlogN) |
O(NlogN) |
O(NlogN) |
O(N) |
yes |
| Insertion Sort | O(N) |
O(N^2) |
O(N^2) |
O(1) |
yes |
| Selection Sort | O(N^2) |
O(N^2) |
O(N^2) |
O(1) |
yes |
| Heapsort | O(NlogN) |
O(NlogN) |
O(NlogN) |
O(1) |
no |
| Timsort | O(N) |
O(NlogN) |
O(NlogN) |
O(N) |
yes |