  In this work we introduce a quantum sorting algorithm with adaptable
requirements of memory and circuit depth, and then use it to develop a new
quantum version of the classical machine learning algorithm known as k-nearest
neighbors (k-NN). Both the efficiency and performance of this new quantum
version of the k-NN algorithm are compared to those of the classical k-NN and
another quantum version proposed by Schuld et al. \cite{Int13}. Results show
that the efficiency of both quantum algorithms is similar to each other and
superior to that of the classical algorithm. On the other hand, the performance
of our proposed quantum k-NN algorithm is superior to the one proposed by
Schuld et al. and similar to that of the classical k-NN.
