## Question: Question:

Can a quantum algorithm be asymptotically faster than a sequential classical algorithm when sorting into a randomly accessible array?

## Answer: Answer:

When limited to comparative sorting, the time complexity of the quantum algorithm for an array of length n is Ω (n log n) ^{[1]} , so it is asymptotically the same as in the classical algorithm.

I don't know much about "what if it's not a comparative sort?" Or "what if I impose other restrictions?" According to the English Wikipedia "Quantum sort" , quanta may be more advantageous when space is limited.

- Høyer, P., Neerbek, J., Shi, Y. (2001). "Quantum complexities of ordered searching, sorting, and element distinctness". 28th International Colloquium on Automata, Languages, and Programming. Pp. 62–73. ArXiv : quant-ph / 0102078. Doi: 10.1007 / 3-540-48224-5_29 .