# What is the current state of the art in quantum sorting algorithms?

As a result of an excellent answer to my question on quantum bogosort, I was wondering what is the current state of the art in quantum algorithms for sorting.

To be precise, sorting is here defined as the following problem:

Given an array $$A$$ of integers (feel free to choose your representation of $$A$$, but be clear about this, I think this already is non-trivial!) of size $$n$$, we wish to transform this array into the array $$A_s$$ such that the arrays 'are reshufflings of each other's and $$A_s$$ is sorted, i.e. $$A_s[i]\leq A_s[j]$$ for all $$i\leq j$$.

What is known about this? Are there complexity bounds or conjectures for certain models? Are there practical algorithms? Can we beat classical sorting (even the bucket or radix sort at their own game? (i.e. in the cases where they work well?))

For comparison-based sorting (and search) bounds seem to fit the ones of classical computers: $\Omega(N\log N)$ for sorting and $\Omega(\log N)$ for search, as shown by Hoyer et al. A couple of quantum sorting algorithms are listed in 'Related work' section of "Quantum sort algorithm based on entanglement qubits {00, 11}".