There are several ways to do this with verying performance and design elegance characteristics, but the main idea is to tag each String with its index before sorting.
One way would be to create a class implementing Comparable that stores the String and its natural (starting) index. Then you can use the Arrays.sort(Object[]) method to sort an array of those.
An old school way would be to create a second array of the indexes and write your own sort routine that rearranges the second array in the same way it does the array of Strings. But who writes their own sorting routines anymore?