(and ignoring duplicates altogether).

Of course it ignores duplicates. There might not be any. As with most such analysis, it also ignores the possibility that the input is already sorted.

It only addresses your remark that duplicates could be removed on output to spill files, as well as during the merge operation.

It would be interesting to see what difference your modifications to the classic algorithm would make in use.

Your computations involving N and S seem to be wandering around thinking that merge sort is something other than O(N*log(N))

Hm. If there was no scope for achieving better than O(N log N) with your "early de-duplications", then this discussion would be entirely moot.

The reason for separating out the merge step, is because if you've already eliminated some duplicates during the spill, then the N involved in the merge is reduced from the input N. But, the unquantifiable bit, is how many of the duplicates were eliminated.

As far as I can see, the only way you could achieve O(N log U), is if you could eliminate the duplicates without ever performing a comparison to find them. Seeing is believing.