Algorithm for sorting pairs of items
I believe you can solve it by: 


first sorting the list that you have with some predictable ordering of the names. (maybe A -> Z)
Doing the final sort later, and to find the "previous" element thru name you just have to do a binary search on the ordered list.