Сам массив переставлять не обязательно, Вам это уже сказали и я не стал повторяться. Достаточно построить индексы к массиву в нужном порядке (или отсортировать индексы в нужном порядке). Списков индексов кстати может быть и больше одного - и массив будет независимо упорядочен сразу по многим критериям, что с перестановками внутри исходного массива невозможно.
Я же добавил что под упорядочить не обязательно понимать отношение именно больше-меньше, достаточно вообще любого отношения над парой элементов (и не обязательно исходного массива), упорядочивающего (в любом желаемом смысле) эту пару. Если для любой пары мы всегда можем выбрать один из её элементов - этого достаточно для сортировки.
(Оффтоп)
В том смысле что не обязательно оценивать ключ сортировки численно, если мы из двух любых картин можем выбрать более красивую, не оценивая саму красоту картин в числах - мы уже можем отсортировать любой список картин по красоте, так и не переводя её для этого в цифру. Хотя, потом конечно легко можем перенумеровать и получить именно что в цифрах ... Об этом часто забывают, что сортировать/упорядочивать можно не только числовые данные, а любые, на которых определено хоть какое-то отношение порядка пар элементов. И за то самое гарантированное (в
смысле) время.
Впрочем, может быть любое отношение порядка является тем же самым отношением больше-меньше - и тогда я зря влез и ввёл в заблуждение.
можно упорядочить (в том же смысле!) и массив длиной 
таких же элементов. Реально сравнивать при этом пары элементов или любым другим образом получать информацию об их порядке (конкретной пары) - роли не играет.
