A commonly used algorithm that totally blew me away when I first encountered it was the Burrows-Wheeler transform for lossless string compression. [0] It rearranges characters in long input strings to increase compressibility by placing repeat characters closer together (you could do so with sorting too, but then lose the ability to recreate the original without associate metadata). Bloom Filters are a close second.
In terms of elegance, I believe it is a fight between CoDel [1] and Union-Find [2].
Speaking of Skip Lists, see also Fenwick Trees, not similar but you'd find them particularly interesting [3].
Also, on the topic of Splay Trees, because we are on Y Combinator, we mustn't go without mentioning Zippers [4].
In terms of elegance, I believe it is a fight between CoDel [1] and Union-Find [2].
Speaking of Skip Lists, see also Fenwick Trees, not similar but you'd find them particularly interesting [3].
Also, on the topic of Splay Trees, because we are on Y Combinator, we mustn't go without mentioning Zippers [4].
[0] https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...
[1] https://queue.acm.org/detail.cfm?id=2839461
[2] https://algs4.cs.princeton.edu/15uf/
[3] https://cp-algorithms.com/data_structures/fenwick.html
[4] https://stackoverflow.com/questions/380438/what-is-the-zippe...