Well, Wikipedia is obviously wrong there. I've fixed it to say number of comparison operations: https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=p...

Note also that in computational complexity theory, "n" is the length of the input in bits: if you have k strings each of length l, using a regular sort, with a comparison subroutine that takes O(l) time, will take O(kl log k) time — O(k log k) operations each taking O(l) time — which, as n=kl, is O(n log k), upper-bounded by O(n log n).

————

I looked up a couple of influential algorithms textbooks in the meantime, and I must admit this is less clear than I'd have liked (though complexity theorists are very aware of it).

• TAOCP vol 3 (which starts with Chapter 5, Sorting) says, on page 5 (in the introduction section of the chapter, where he often says things informally and not exactly):

> The time required to sort N records, using a decent general-purpose sorting algorithm, is roughly proportional to NlogN; we make about logN “passes” over the data. This is the minimum possible time, as we shall see in Section 5.3.1, if the records are in random order and if sorting is done by pairwise comparisons of keys. Thus if we double the number of records, it will take a little more than twice as long to sort them, all other things being equal. (Actually, as N approaches infinity, a better indication of the time needed to sort is N(logN)^2, if the keys are distinct, since the size of the keys must grow at least as fast as logN; but for practical purposes, N never really approaches infinity.)

It's emphasized less than I'd have liked but he has already mentioned your observation though (and I checked this was present in the first edition in 1973). BTW, note no "O" here: where possible he actually gives the number of machine operations, including the constant factor. TAOCP is very much a "nothing up my sleeve" book, where everything is analyzed down to the constants (where possible) and machine code given.

He starts with a very concrete problem where what's being sorted are numbers that each fit in a machine word:

> “Memory locations R+1, R+2, R+3, R+4, and R+5 contain five numbers. Write a computer program that rearranges these numbers, if necessary, so that they are in ascending order.”

and he makes it clear that what's being sorted are records that contain keys and satellite information, and he's going to mostly assume the keys are integers that fit in a word, sometimes even part of a word. The mention of sorting strings (can get there via the index) is an exercise on page 178:

> Design an algorithm to sort strings α1, ..., αn on an m-letter alphabet into lexicographic order. The total running time of your algorithm should be O(m+n+N), where N = |α1| + · · · + |αn| is the total length of all the strings.

Note that this running time is better than O(n (N/n) log n) — assuming that the strings are of about equal length N/n, and using a standard sorting algorithm — that I mentioned above. The solution is essentially to construct a trie.

• CLRS starts its sorting section with "A sequence of n numbers" and has:

> A sorting algorithm describes the method by which we
determine the sorted order, regardless of whether we are sorting individual numbers or large records containing many bytes of satellite data. Thus, when focusing on the problem of sorting, we typically assume that the input consists only of numbers. Translating an algorithm for sorting numbers into a program for sorting records…

Its index on sorting variable-length items points to p206 (in the 3rd edition) where, similar to TAOCP:

> 8-3 Sorting variable-length items

> a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time.

> b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.