Although hashmaps are O(n) in practice, they can be worse than O(n log n) on some rare inputs that cause lots of hash collisions. Several sorting algorithms suc

Although hashmaps are O(n) in practice, they can be worse than O(n log n) on some rare inputs that cause lots of hash collisions. Several sorting algorithms such as mergesort and heapsort are guaranteed O(n log n).