<p>If you are speaking specifically of sorting lists of integers on a multitape TM, then I think the answer is no. For example, comparison-based sorts, when implemented on a TM and sorting integers of bit-length <span class="math-container">$w$</span>, take <span class="math-container">$\Theta(n w \log n)$</span> time, b/c it takes <span class="math-container">$\Theta(w)$</span> to compare two <span class="math-container">$w$</span>-bit integers. But radix sort takes <span class="math-container">$O(nw)$</span> time, which is optimal as it is linear in the input size (assuming all the integers have the same number of bits).</p>
<p>See also fusion trees (but I think those are in the word RAM model and I'd have to carefully think through its translation to multitape TMs...)</p>

CC BY-SA 4.0
2023-02-17T18:20:20.150Z
That said, I was excited to see Jan's answer in a restricted model of TMs!
Joshua Grochow
CC BY-SA 4.0
2023-02-20T09:20:49.567Z
For the word RAM it depends on the exact variation of RAM you are using. But sorting n integers where the word length w is O(log(n)) takes times O(n) with a simple algorithm. For very large w (i.e. way bigger than log(n)) I think the question is open but you have a n × √log(log(n)) expected time and a n×log(log(n)) exact time one.
[1] https://link.springer.com/article/10.1007/BF02127798 
[2] https://ieeexplore.ieee.org/document/1181890
Louis
CC BY-SA 4.0
2023-02-17T18:15:56.087Z
2023-02-17T18:15:56.087Z
Joshua Grochow
<p>The paper &quot;<a href="https://doi.org/10.1007/978-3-540-88282-4_39" rel="nofollow noreferrer">Sorting and Element Distinctness on One-Way Turing Machines</a>&quot; by Holger Petersen shows a lower bound for sorting on a Turing machine with one work tape and one-way input.</p>

CC BY-SA 4.0
2023-02-17T14:44:05.243Z
2023-02-17T14:44:05.243Z
Jan Johannsen
<p>Can we prove the lower bound for the sorting problem just by Turing machine model?
It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can model it by decision tree and establish the lower bound of the number of comparisons.</p>

<cc.complexity-theory><turing-machines><sorting><decision-trees>
Lower bound for sorting without using a decision tree model
Hao Huang
# Lower bound for sorting without using a decision tree model

(Asked by: username_0 on 2023-02-17)

Can we prove the lower bound for the sorting problem just by Turing machine model?
It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can model it by decision tree and establish the lower bound of the number of comparisons.

**Tags:** cc.complexity-theory, turing-machines, sorting, decision-trees

---

## 2 answers

### Answer by username_1 on 2023-02-17. Score: 3

If you are speaking specifically of sorting lists of integers on a multitape TM, then I think the answer is no. For example, comparison-based sorts, when implemented on a TM and sorting integers of bit-length $w$, take $\Theta(n w \log n)$ time, b/c it takes $\Theta(w)$ to compare two $w$-bit integers. But radix sort takes $O(nw)$ time, which is optimal as it is linear in the input size (assuming all the integers have the same number of bits).

See also fusion trees (but I think those are in the word RAM model and I'd have to carefully think through its translation to multitape TMs...)

> **Comments:**
> **username_1**: That said, I was excited to see Jan's answer in a restricted model of TMs!  
> **username_2**: For the word RAM it depends on the exact variation of RAM you are using. But sorting n integers where the word length w is O(log(n)) takes times O(n) with a simple algorithm. For very large w (i.e. way bigger than log(n)) I think the question is open but you have a n × √log(log(n)) expected time and a n×log(log(n)) exact time one. [1] https://link.springer.com/article/10.1007/BF02127798  [2] https://ieeexplore.ieee.org/document/1181890  

---

### Answer by username_3 on 2023-02-17. Score: 2

The paper "[Sorting and Element Distinctness on One-Way Turing Machines](https://doi.org/10.1007/978-3-540-88282-4_39)" by Holger Petersen shows a lower bound for sorting on a Turing machine with one work tape and one-way input.


---

