Deduping a file of size X/30 against a sorted file of size X should take time (X/30) * log x * n, since the lookups benefit from binary search due to the sort and you only need to do X/30 of the lookups.

This should be significantly smaller, by a factor of 10 at least and likely a factor of 30, vs sorting X records. You probably have the same Big O but doing it on less data.