In the worst case, you need to insert every element into your set to find out if there's no duplicate hence it'll take O(n log n) too

Not with a hash set - that gives you expected amortized O(1) insertion (yes, both expected and amortized). In contrast, a generalized sort is O(n log n), but you can sort numeric types in O(n).