Merge multiple lists with variable length "popping" elements from each

Question

I'd like to sort multiple lists (variable number of them) into single list, but keeping the specific order. For example:

List A: { 1,2,3,4,5 }
List B: { 6,7,8 }
List C: { 9,10,11,12 }

Result List: { 1,6,9,2,7,10,3,8,11,4,12,5 }

The only idea I got was to remove the first element from each list and put it into resulting set (and repeat until all lists are empty), but maybe there is a better way that doesn't require to create copy of each list and doesn't affect the original lists as well?

Answer 1

I suggest using IEnumerator<T> to enumerate lists while they have items:

private static IEnumerable<T> Merge<T>(params IEnumerable<T>[] sources) {
  List<IEnumerator<T>> enums = sources
    .Select(source => source.GetEnumerator())
    .ToList();

  try {
    while (enums.Any()) {
      for (int i = 0; i < enums.Count;)
        if (enums[i].MoveNext()) {
          yield return enums[i].Current;

          i += 1;
        }
        else {
          // exhausted, let's remove enumerator
          enums[i].Dispose();
          enums.RemoveAt(i);
        }
    }
  }
  finally {
    foreach (var en in enums)
      en.Dispose();
  }
}

Test

List<int> A = new List<int>() { 1, 2, 3, 4, 5 };
List<int> B = new List<int>() { 6, 7, 8 };
List<int> C = new List<int>() { 9, 10, 11, 12 };

var result = Merge(A, B, C)
  .ToList();

Console.Write(string.Join(", ", result));

The outcome is

1, 6, 9, 2, 7, 10, 3, 8, 11, 4, 12, 5

Answer 2

For more flexible use

 public static string MergeArrays(params IList<int>[] items)
    {

        var result = new List<int>();
        for (var i = 0; i < items.Max(x => x.Count); i++)
            result.AddRange(from rowList in items where rowList.Count > i select rowList[i]);

        return string.Join(",", result);
    }

.

        var a = new List<int>() { 1, 2, 3, 4, 5 };
        var b = new List<int>() { 6, 7, 8 };
        var c = new List<int>() { 9, 10, 11, 12, 0, 2, 1 };

        var r = MergeArrays(a, b, c);