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.