Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-331 | 22nd November 2026 12:37

Sorting in $o(N\log N)$ Time on a Multitape Turing Machine

RSS-Feed




TR26-331
Authors: Yann Tal
Publication: 22nd November 2026 15:34
Downloads: 35
Keywords: 


Abstract:

We give a deterministic algorithm that stably sorts $n$ binary keys of arbitrary lengths on a fixed multitape Turing machine, carrying along any associated data. It also sorts signed numbers in numerical order given their finite expansions in any fixed base. If $N$ is the total encoded input length in bits, including the associated data, the algorithm uses $O\left(\frac{N\log n}{(\log\log\log n)^{\eta}}\right)$ time and $O(N)$ space for an explicit absolute constant $\eta>0$. The worst-case running time is therefore $o(N\log N)$. A deterministic algorithm that sorts by comparing keys and copies each output bit from the corresponding bit of its input item requires $\Omega(N\log N)$ tape steps in the worst case.

Applying the reduction of Harvey and van der Hoeven to OpenAI's integer multiplication algorithm yields an improved time bound for matrix transposition on a multitape Turing machine. We adapt the external-memory sorting algorithm of Li, Li and Liu, using transposition to group keys by their next digit on tape. At each step we distribute the items across rows so that most fit in columns reserved for their current digit. Within each row we split the items into pieces so that most pieces can be copied in order. Transposing the layout then brings together items with the same digit.



ISSN 1433-8092 | Imprint