Does it? Set insertion is O(log n) and you need to insert n items.
let mut hash_set = HashSet::new();
let mut len = 0;
for i in 0..arr.len() {
if !hash_set.contains(&arr[i]) {
hash_set.insert(arr[i]);
arr[len] = arr[i];
len += 1;
}
}
arr.truncate(len);You can also use radix sort for what I'd like to call "fake" O(n) sort since physical hardware puts an upper limit on the hidden constant.