How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access... how much does losing that cost us? Also, MTMs can't use log-sized words.

Say we have $N$ integers from $[0, 2^B)$. It's not too hard to adapt existing sorting algorithms to get an upper bound on the sorting time. A radix sort would normally take $O(B N)$ time, but on an MTM we have to store the bits of the integers. This increases the cost of moving items by a factor of $B$, giving an actual running time of $O(B^2 N)$ operations for radix sort on an MTM. Merge sort and quick sort also have their runtimes expand by a factor of $B$ due to item movement, from $O(N \log N)$ to $O(B N \log N)$.

Since $O(B N \log N)$ is better than $O(B^2 N)$ in some cases and worse in others, we can alternate strategies to sort on an MTM in $O(B N \min(B, \log N))$ time.

Is that bound tight, or is there some way to avoid moving items so much? Does sorting $N$ integers of size $B$ take $\Theta(B N \min(B, \log N))$ time on MTMs?

  • $\begingroup$ Not sure if it's tight. But those are the same two algorithms given by the textbook "Reischuk, K.R.: Einführung in die Komplexitätstheorie. B. G. Teubner (1990)". $\endgroup$ Oct 9 '20 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.