Algorithm for sorting pairs of items

Question

I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem is that any two random nodes will not tell me anything about their order unless they happen to lie next to each other, so I can't use a traditional sorting algorithm.

When I try to work through ideas everything basically comes down to "grab" the node at the start and then place it after the correct node" then repeat with the next node at start of the list. The problem is this has worse case running time of $O(n^2)$ complexity if the items are reversed. Any ideas of how to efficiently solve a problem like this?

Answer 1

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.