Enhver sammenligningsalgoritme må ta tid i verste tilfelle. Dette var tilfellet for Quicksort og Merge-Sort. I dette kapittelet skal vi gjøre antagelser som lar oss sortere i linear tid.
Sammenligningsalgoritme Counting Sort
- Antar at vi vet det største tallet Radix-Sort
- Antar at vi vet lengden på elementene i listen. Bucket Sort
- Antar uniformt fordelte tall i området Randomized Select