How to merge an array that was split into 2 arrays with odd and even indices?

Question

From this Q: How to split an array to 2 arrays with odd and even indices respectively?

I have used this method to split an array into 2 arrays with odd and even indices respectively:

int[] a = new int[] { 1, 3, 7, 8 };

int[] aEven = a.Where((x, i) => i % 2 == 0).ToArray();
int[] aOdd = a.Where((x, i) => i % 2 != 0).ToArray();

This results 2 arrays:

aEven : {1, 7}
aOdd  : {3, 8}

How can I merge the aEven/aOdd back to be the same like the original a array in an elegant way?

NOTE: I'm not changing the aEven/aOdd arrays, and it is guaranteed both arrays have the same length.

The output I need from aEven/aOdd inputs is:

{ 1, 3, 7, 8 };

Answer 1

One way to do this is by combining Enumerable.Zip and Enumerable.Aggregate along with a little finessing. Note that this still uses loops under the hood.

var aList = aEven.Zip(aOdd, (even, odd) => new {even, odd})
                 .Aggregate(new List<int>(aEven.Length + aOdd.Length),
                            (list, z) =>
                            {
                                list.Add(z.even);
                                list.Add(z.odd);
                                return list;
                            });
if (aEven.Length != aOdd.Length)
    aList.Add(aEven[aEven.Length-1]);

var aOutput = aList.ToArray();

for (var i = 0; i < aOutput.Length; ++i)
    Console.WriteLine($"aOutput[{i}] ==> {aOutput[i]} == {a[i]} <== a[{i}]");

This only works in your scenario however (splitting out and then restoring an array by odd/even indices, assuming that the order of the 'sub-arrays' has been maintained).

The resultant arrays will either have the same size (the original array had an even number of items) or the even array will have one extra item (the original array had an odd number of items). In the latter case, the extra item will be dropped by Zip and needs to be manually accounted for. This won't work for other scenarios where your two sub-arrays were calculated via other means.

You can also do it without the intermediate list, using a pre-allocated array but you'd have to keep track of the index outside of the LINQ calls (which I don't like as much):

var index = 0;
var aOutput = aEven.Zip(aOdd, (even, odd) => new {even, odd})
                   .Aggregate(new int[aEven.Length + aOdd.Length],
                             (arr, z) =>
                             {
                                 arr[index++] = z.even;
                                 arr[index++] = z.odd;
                                 return arr;
                             });
if (aEven.Length != aOdd.Length)
    aOutput[index] = aEven[aEven.Length-1];

Another way to do it would be to use a combination of Zip, SelectMany and Concat (to account for the last item):

var aOutput = aEven.Zip(aOdd, (even, odd) => new[]{ even, odd })
    .SelectMany(z => z)
    .Concat(aEven.Length == aOdd.Length ? new int[0] : new []{ aEven[aEven.Length - 1] })
    .ToArray();

A straightforward for loop would still probably be the simplest solution.

Answer 2

Just use for loop instead. It won't create all these intermediate arrays of tuples, while is comparably readable and requires the same amount of code.

int[] Merge(int[] evenItems, int[] oddItems)
{
    var itemsCount = evenItems.Length + oddItems.Length;
    var result = new int[itemsCount];

    for (var i = 0; i < itemsCount; i++)
    {
        var sourceIndex = Math.DivRem(i, 2, out var remainder);
        var source = remainder == 0 ? evenItems : oddItems;
        result[i] = source[sourceIndex];
    }

    return result;
}

Answer 3

public static IEnumerable<T> MergeByZipAndRemainder<T>(T[] this firsts, T[] seconds)
{
  int maxLength = Math.Max(firsts.Length, seconds.Length);
  foreach(int i in Enumerable.Range(0, maxLength))
  {
     if (i < firsts.Length) { yield return firsts[i]; }
     if (i < seconds.Length) { yield return seconds[i]; }
  }
}

Then:

var result = evens.MergeByZipAndRemainder(odds).ToArray();

This approach meets several of the criticisms of the answerers.

• It is elegant.
• It addresses the general case of merging arrays which may be very different in length.
• It only enumerates once O(N+M).
• It does not allocate intermediate array objects which will require garbage collection.
• It should be faster on paper, but I have not measured the performance.

Answer 4

Create InterlockWith extension method, and yes, there's no escape from loops:

public static IEnumerable<T> InterlockWith<T>(this IEnumerable<T> seq1, IEnumerable<T> seq2)
    {
        Tuple<T[], int>[] metaSequences = new Tuple<T[], int>[2];
        metaSequences[0] = Tuple.Create(seq1.ToArray(), seq1.Count());
        metaSequences[1] = Tuple.Create(seq2.ToArray(), seq2.Count());
        var orderedMetas = metaSequences.OrderBy(x => x.Item2).ToArray();

        for (int i = 0; i < orderedMetas[0].Item2; i++)
        {
            yield return metaSequences[0].Item1[i];
            yield return metaSequences[1].Item1[i];
        }

        var remainingItems = orderedMetas[1].Item1.Skip(orderedMetas[0].Item2);
        foreach (var item in remainingItems)
        {
            yield return item;
        }
    }

You can get your result set by calling it like this:

a = aEven.InterlockWith(aOdd).ToArray();

Answer 5

var merged = evens
  .Zip(odds, (even, odd) => new [] {even, odd})
  .SelectMany(pair => pair)
  .Concat(evens.Skip(odds.Length))
  .ToArray();

Answer 6

First you can merge them by using Concat, and then if you want the reslt to be sorted, you can use OrderBy :

aEven.Concat(aOdd).OrderBy(b => b).ToArray();