The complexities don't multiply here.

I never said that. I just mentioned that O(n log(n)) is the lower bound since sorting will already take that long.

What I'm concerned with is the complexity of the scanning step, which I think might be more than O(n log(n)) on its own (and therefore more than O(n log(n)) overall)

At least I'd like to see an explanation why it's <= O(n log(n))