# How can I sort a list of integer pairs in sequence?

I have a list of paired integers, every nth integer paired with every nth+1 integer. I'm trying to sort the list such that the pairs form a chain. For example:

Input: {12,72, 38,2, 72,38, 2,12} Output: {38,2, 2,12, 12,72, 72,38}

The trick is that the list may contain several unconnected chains. The chains don't need to be in any sequence, just the pairs within each chain. As per the input, each chain should be a loop unless they chain has only one pair, so any pair in the chain should be a valid first pair.

What I've tried is this (C#):

int a = 0;
int b = 0;
int temp;

while (a < list.Count) {
b = a + 2;
while (b < list.Count) {
if (list[b] == list[a + 1]) {
temp = list[b];
list.RemoveAt(b);
list.Insert(a + 2, temp);

temp = list[b + 1];
list.RemoveAt(b + 1);
list.Insert(a + 3, temp);

a += 2;
b = a;
}
b += 2;
}
a += 2;
}


Which is giving me mostly correct results, but is still leaving the list with some disconnected pairs that should be part of a chain.

I'm not great with sorting algorithms and this has proven to be a difficult problem to google, so I'm hoping someone can point out the flaw in my code or point me in the right direction for research.

• This looks like a general programming problem that doesn't use any game-specific concepts - you might find you get more answers faster by asking this type of question on StackOverflow instead, since they get far more traffic than we do. – DMGregory Mar 26 at 10:36
• I did. Several people told me my question was too general, closed my question, then asked me why I couldn't just decide to need different output. People here have always been very helpful and understanding. StackOverflow, not so much. – IanLarson Mar 26 at 17:57

The result is that an example like { 1,2, 0,1, 2,3} will sort to {1,2, 2,3, 0,1} instead of {0,1, 1,2, 2,3}, so links might be split up. You could check whether the pair at b comes before the pair at a, but with circular links being legal, you need to check for the case where the whole list is one long circular chain, which could result in infinite loops.