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?))