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?


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.