Sorting suffers from scale, because if you double the amount of things to sort you also double the number of places each item can go, so it becomes more complex rather than being more efficient.
Big O notation indicates the worst-case scenario for algorithms.
A bad sorting algorithm is called Bubble sort, only slightly better is Insertion sort.
A good one is Mergesort where you break items into pairs, then sorted pairs, then sorted 4ths etc.
Chapter notes
- In heads-up poker, there has to be disagreement about sorting for games to happen
- Pecking orders are preemptive violence
- Quantifiable outcomes enables one-off comparisons rather than many pairwise sorts
- Benchmarks for national status can prevent military disputes
References
- Chapter 3 of Algorithms to live by