Сортировка на листе работает с индексом строки, а не с самой строкой. Так что для ускорения сортировки строкового массива придётся создать индексный массив Long-ов и использовать именно его при сортировке. Как я понимаю, исходный массив полностью находится в памяти? тогда, вероятно, qsort.
А по окончании сортировки использовать быстрое упорядочивание - и это может оказаться самым длительным этапом.