[mountainreason]

Wouldn't you at least be looking at nlog(n) for the sort in the merge join?

[umanwizard]

Yes, if the data is not already sorted. Thus it's O(n) for already sorted data and O(n log(n) + n) -- which simplifies to O(n log(n)) -- for arbitrary data.

[mountainreason]

Yeah. I know. Why would the data already be sorted?

[umanwizard]

In a database you might have already built an index on that data.