Sorting takes that much time, it even says so under "Properties and relations" in the documentation for DeleteDuplicates.

@Pickett That makes no sense, this is a bug.

@pickett try sorting 50 million records in any other system (and then remember that the sort is done in C in mathematica, especially with the system ordering (as opposed to a user function - in the latter case, taking longer would not surprise me).

If they've put an example in the documentation where DeleteDuplicates is ~170 times faster, and they explicitly say that this is because of the sorting, then it can hardly be considered a bug. It obviously made sense to whoever wrote the documentation.

@Pickett evaluate {First[Timing[Sort@DeleteDuplicates[list]]], First[Timing[Union[list]]]} and you will see that this is likely to be a bug.

@paw I did try that; but I didn't draw the conclusion that it was a bug, just that the Union algorithm required some other kind of sorting. Because when I ran that test I didn't get the substantial decrease in performance that the documentation tells me I should get.

@paw Precisely. And in any case, a documented bug is still a bug.

@IgorRivin Then ask WRI and see what they say. The only way to get a more canonical answer than the documentation is to get someone at WRI to answer.

@Pickett the documentation makes no sense. This is not some NP-hard problem we are dealing with, but the most studied problem in all of computer science, which was well understood forty(!!!) years ago.

Union and DeleteDuplicates are not the same. Since Union sorts, in uses O(N log N) algorithm. OTOH, DeleteDuplicates can use O(N) algorithm. For lists as large as yours, it can make a difference.

I don't know if Union is unnecessarily slow. To elaborate on the remark by @Pickett, applying DeleteDuplicates before sorting does not demonstrate anything beyond what was already known-- that it is much faster than Sort. Once the list has been culled, sorting should be fast. Union, in constrast, sorts first and then eliminates neighbors that are SameQ.

As noted by @Leonid Shifrin, there is a noable complexity difference. In this case it could account for a factor of 20 or so (natural log of 5*10^7). Since the actual factor is closer to 200 either there is a fairly big constant for sorting, or there is a bottleneck in Sort. I do not know which is the case.

@LeonidShifrin 50000000 log(base 2) 50000000 is a little over 1BN. Yes, there is overhead, but no way should this take much more than a second on modern hardware (try unix sort for comparison). As for DeleteDuplicates, the algorithm is still $O(N \log N),$ (I can only assume it uses hashing), perhaps with smaller hidden constants in some use cases, and perhaps with larger constants in others. (hashing is a more complicated operation than comparison).

@IgorRivin I was told once that there was a certain O(N) algorithm used in DeleteDuplicates (or so I recall), but admittedly I don't know the details, and I don't know how it would have to operate to be O(N), off the top of my head.

@LeonidShifrin With enough space available, I don't see why a hash table alg. should take more than O(N)

@belisarius No, Igor meant that it is O(log N) for each element, and there are N elements.

@belisarius Ok, sorry, I see what you mean - that effectively we may make hash lookup (almost) O(1).

@belisarius With $N$ elements, how big should your hash keys be? You can't get out of $N \log N.$

On my laptop, sorting a list of 5 million real numbers between 0 and 1000 takes about 5 seconds in Mathematica. So I think any complaints about speed should be directed at Sort's performance, rather than Union's performance. In other words, a better question title might be "A more perfect Sort", rather than "A more perfect Union".

The lookup time O(log N) is an amortized lookup, when you grow the hash table and have to rehash from time to time. This is the case where you don't know the size of the hash table in advance. If you know the needed capacity in advance, the element lookup of modern hash table implementations is O(1).

What @Leonid Shifrin said. For practical purposes DeleteDuplicates is O(n). In order to be worse there would need to be either size constraints on hash table size or a very unlucky hash function. Growing the table is not an issue provided it grows geometrically (which it does). Hashing time is, properly speaking, not a factor (in either colloquial or complexity sense). It can depend on size of the inputs but they are fixed and, for purposes of comparison with Sort, operations on the elements are regarded as constant time.

Evidence of me falling into this trap: chat.stackexchange.com/transcript/message/13085665#13085665. That was mostly me being silly (as admitted :P ). I guess it is indeed a trap to think that if you want to Sort+DeleteDuplicates, Union must be faster. Whereas deleting duplicates and then sorting can be faster. Perhaps it should say so in the documentation of Union.