As for your first example “you may be relying on a 3rd party service that compares things”, has this ever happened in the history of the universe?
As for your first example “you may be relying on a 3rd party service that compares things”, has this ever happened in the history of the universe?
Imagine you want to dedupe 1000 text documents each 1TB in size. Hashing naively would require reading 1000 TB and would be horribly inefficient. Hashing the short prefix would be better but you need to know how long of a prefix is sufficient to avoid too many collisions.
Sorting might be safer from efficiency perspective in this case unless you know a bit more about your data set.
About 3rd party service: let's say you have images of faces and you want to dedupe them. A third party face comparison service could be a reasonable option. (And as another comment suggested, third party could be a different group in the same company, whose code base isn't trivial to modify.)
Of course, in a highly specialized distribution, all the strings could be identical except for the last few characters, and then sorting would be horrible.
Ultimately you have to have some idea about the distribution of your data to say anything about average complexity.