Semisorting, and then running a filter to remove duplicates (which will be consecutive after the semisort) can solve this problem in O(n) expected work & space

Semisorting, and then running a filter to remove duplicates (which will be consecutive after the semisort) can solve this problem in O(n) expected work & space and O(log n) depth w.h.p. AFAIK the approach is reasonably practical as well. Note that the algorithm is not in-place. Paper: https://people.csail.mit.edu/jshun/semisort.pdf https://people.csail.mit.edu/jshun/semisort.pdf