| Sorting | Avg | Best | Worst | Space | Stable |
|---|---|---|---|---|---|
| Quicksort | nlogn | n | n^2 | logn -- n | No, can be |
| Merge sort | nlogn | nlogn | nlogn | n | Y |
| Heapsort | nlogn | nlogn | nlogn | 1 | N |
| Insertion sort | n^2 | n | n^2 | 1 | Y |
| Selection sort | n^2 | n^2 | n^2 | 1 | N |
| Bubble sort | n^2 | n | n^2 | 1 | Y |
| Counting/Radix | nk/d | nk/d | nk/d | 2^d | Y |