| Algorytm | Złożoność czasowa (czas oczekiwany) |
Złożoność czasowa (czas pesymistyczny) |
Złożoność czasowa (czas optymistyczny) |
Złożoność pamięciowa | Stabilny | Przez porównanie |
|---|---|---|---|---|---|---|
| Bubble sort | O(n2) | O(n2) | O(n2) | O(1) | TAK | TAK |
| Insertion sort | O(n2) | O(n2) | O(n) | O(1) | TAK | TAK |
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) | NIE[3] | TAK |
| Counting sort | O(n+k)[1] | O(n+k)[1] | O(n+k)[1] | O(k) | TAK | NIE |
| Merge sort | O(n*log n) | O(n*log n) | O(n*log n) | O(n) | TAK | TAK |
| Quick sort | O(n*log n) | O(n2) | O(n*log n) | O(1) | NIE[3] | TAK |
| Heap sort | O(n*log n) | O(n*log n) | O(n*log n) | O(1) | NIE | TAK |
| Radix sort | O((n+b)*logb(k))[1][2] | O((n+b)*logb(k))[1][2] | O((n+b)*logb(k))[1][2] | O(n+b) | TAK | NIE |
[1] k - moc zbioru do którego należą elementy
[2] b - podstawa systemu liczbowego (zależy od implementacji)
[3] Istnieją implementacje stabilne, ale wymagają dodatkowe O(n) pamięci