Создать хэш-массив, где индексом будет нижний массив, а значением - верхний.
Отсортировать нижний массив стандартным методом, встроенным в язык.
Далее пройти по хэш-массиву, выдёргивая значения элементов, где индексами будет отсортированный нижний массив.
Второй вариант:
Преобразовать это дело в один массив такого вида: ["2-q2w", "1-mmm1e", "4-m4hr", "3-c3s"];
(минус - в рои разделителя). Отсортировать. Вывести правую часть - то, что после минуса.