I need your help geeks. ;) Programming language is irrelevant. I'm just trying to come up with a good algorithm for addressing the problem.

I have an array of items. Some items have a number on both sides. I'll call these "matched pairs". The matched pairs are the keystones of this problem. I need to sort the items between the matched pairs in a particular way.

There's a "from number" and a "to number" There may be more from -> nil than nil-> to, or vice-versa. There may also be NO items between the matched pairs.

You can assume that the numbers will always be sorted within their column. E.g. From numbers will go from 1 to x ascending, and to numbers will go from 1 to x ascending. There may be nils inserted along the way though.

# I have this
#   v from number
#          v to number
[
    [nil,  1],
    [1,    2],  # a matched pair
    [2,    nil],
    [3,    nil],
    [4,    nil],
    [5,    nil],
    [nil,  3], # note that there are more 
    [nil,  4], # nil -> to number than 
    [nil,  5], # from number -> nil
    [nil,  6],
    [nil,  7], 
    [6,    8],  # another matched pair
    [7,    9],  # nothing in between
    [8,    nil],# no nil->to number to pair it with
    [9,    10]
]

I need to transform it to this. We're almost, but not quite interleaving the items from each column.

[
    [nil,  1],
    [1,    2],
    [2,    nil],
    [nil,  3],
    [3,    nil],
    [nil,  4],
    [4,    nil],
    [nil,  5],
    [5,    nil],
    [nil,  6],
    [nil,  7],
    [6,    8],
    [7,    9],
    [8,    nil],
    [9,    10]
]

Additional Information that may, or may not, be useful

These numbers represent lines in two documents. In the example above, the text on line 2 in the "from" document was not found in the "to" document. It has been replaced by the text on line 3 ( in the "to" document ). The text on line 3 in the "to" document wasn't found in the "from" document so. So, 2 -> nil (two went away) nil->3 ( three was added ).