Another fun one is radix sort[1]. We used to use it for sorting alpha'd quads(think particle systems/ui/etc) from front-to-back. Easily annihilates anything else in terms of raw performance for datasets < 10,000 with int/f32 keys and it's stable(!) for identical values.

This talk[2] from Herb Sutter(starting at 22:30) is one of my favorite talks and does a great job of explaining why this is so important(and why dense arrays are still king in many areas).

[1] http://stereopsis.com/radix.html

[2] https://channel9.msdn.com/Events/Build/2014/2-661