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.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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory
    Mar 26, 2020 at 10:36
  • \$\begingroup\$ 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. \$\endgroup\$
    – IanLarson
    Mar 26, 2020 at 17:57

1 Answer 1


Your algorithm only appends links to a chain to the first encountered pair in the chain, but it does not ensure a is the first item in the chain.

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.

  • \$\begingroup\$ Apologies, I don't yet have enough rep to clarify my assumptions before posting an answer. Hope this helps! \$\endgroup\$ Mar 26, 2020 at 4:45
  • \$\begingroup\$ Thanks for catching that typo! I think I fixed it. Your assumptions are good, except the second. Circular links are allowed, however, there is no "correct" start or end of a chain. As long as each pair in the chain leads into the next, it's a valid chain. That being said, there should be no need to go backwards, right? Any pair before "a" should have been checked against all other pairs. \$\endgroup\$
    – IanLarson
    Mar 26, 2020 at 18:11
  • 1
    \$\begingroup\$ I think I understand what your saying, but I'm not quite seeing it. The incrementing after the swap sets "a" to the pair that was just swapped in. If no match is found to that pair, "a" is still set to that pair. The incrementing in the outer loop then moves it to the next unconnected pair to start a new chain. \$\endgroup\$
    – IanLarson
    Mar 26, 2020 at 20:11
  • \$\begingroup\$ Also, I'm realizing in my implementation that all valid chains should be loops. I'm checking the functions that determine the input to make sure, but that seems to be the case, which should preclude the situation you added regarding the ordering of the pairs in the chain. I've edited my post to reflect that. \$\endgroup\$
    – IanLarson
    Mar 26, 2020 at 20:16
  • \$\begingroup\$ Yep, that shouldn't be showing up in the input. \$\endgroup\$
    – IanLarson
    Mar 26, 2020 at 21:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .