'Uniqueing' an unsorted list of integers
In practice you can solve this problem easily in linear expected time with a hash table: just hash everything and eliminate the duplicates when they collide with each other. See, e.g. this Python recipe which primarily uses hashing but falls back on other strategies for objects that can't be hashed.

Whether you accept this as an acceptable theoretical answer depends somewhat on your model of computation.