| Algorithm | File | Time | Space |
|---|---|---|---|
| Bubble sort | 1, 2 | Θ(n^2) | Θ(1) |
| Cocktail sort | 1 | O(n^2), Ω(n) | Θ(1) |
| Comb sort | 1 | Ω((n^2)/(2^p))[1] | Θ(1) |
| Gnome sort | 1 | O(n^2), Ω(n) | Θ(1) |
| Heapsort | 1 | Θ(n log n) | Θ(1) |
| Insertion sort | 1 | O(n^2), Ω(n) | Θ(1) |
| Merge sort | 1, 2 | Θ(n log n) | Θ(n) |
| Odd-even sort | 1 | O(n^2), Ω(n) | Θ(1) |
| Quicksort | 1 | O(n^2), Ω(n log n) | O(log n) |
| Selection sort | 1 | O(n^2), Ω(n) | Θ(1) |
[1] Average case, where p = number of increments
| Algorithm | File | Time | Space | Notes |
|---|---|---|---|---|
| Bucket sort | 1 | O(n^2), Ω(n + k), Θ(n + k)[1] | Θ(n + k)[2] | Where k = number of buckets |
| Counting sort | 1 | Θ(n + k) | Θ(k)[3] | Where k = number of possible values |
| Radix sort | 1 | Θ(d(n + k))[4] | Θ(n + k)[4] | Where d = number of digits, k = number of possible values |
[1] Average case
[2] O(n * k) if buckets are allocated space for n elements
[3] O(n + k) if buckets are lists of values instead of a count of values
[4] When the inner stable sort used takes Θ(n + k)