How to optimize function for merging sorted arrays in C#

Question

I write this function for merging two arrays.

private static int[] Merge(int[] array1, int[] array2)
{
    var mergedArray = new int[array1.Length + array2.Length];
    int i = 0, j = 0, k = 0;
    while(k < mergedArray.Length)
    {
        if(i == array1.Length || j == array2.Length)
        {
             if (i <= j)
                {
                    mergedArray[k] = array1[i];
                    i++;
                }
                else
                {
                    mergedArray[k] = array2[j];
                    j++;
                }
        }
        else
        {
            if(array1[i] < array2[j])
            {
                mergedArray[k] = array1[i];
                i++;
            }
            else
            {
                mergedArray[k] = array2[j];
                j++;
            }
        }
        k++;
    }
    return mergedArray;
}

How to reduce if statements in this code?

This is not the same question. The merging here takes into account the values of the arrays, while the possible duplicate only concatenates two arrays. — carlosfigueira
– carlosfigueira, Commented Jul 11, 2012 at 20:33
I think this does more than just merge. Maybe there some sorting going on (if(array1[i]<array2[j]).. statement). Can you please explain more what are you trying to do. — John Alexiou
– John Alexiou, Commented Jul 11, 2012 at 20:33
"Is there a way to simplify this code?" --> codereview.stackexchange.com — CodeCaster
– CodeCaster, Commented Jul 11, 2012 at 20:36
@Victor: Please provide an example set of arrays, and what the expected results are. The intent is not clear from the source what the Merge() function actually does. — John Alexiou
– John Alexiou, Commented Jul 11, 2012 at 20:46

d--b · Accepted Answer · 2012-07-11 21:14:15Z

You can also make a Linq friendly version. This one is fast and will work on IEnumerable. You could easily translate this to any type T where T is IComparable.

    private static IEnumerable<int> Merge(IEnumerable<int> enum1, IEnumerable<int> enum2)
    {
        IEnumerator<int> e1 = enum1.GetEnumerator();
        IEnumerator<int> e2 = enum2.GetEnumerator();

        bool remaining1 = e1.MoveNext();
        bool remaining2 = e2.MoveNext();

        while (remaining1 || remaining2)
        {
            if (remaining1 && remaining2)
            {
                if (e1.Current > e2.Current)
                {
                    yield return e2.Current;
                    remaining2 = e2.MoveNext();
                }
                else
                {
                    yield return e1.Current;
                    remaining1 = e1.MoveNext();
                }
            }
            else if (remaining2)
            {
                yield return e2.Current;
                remaining2 = e2.MoveNext();
            }
            else
            {
                yield return e1.Current;
                remaining1 = e1.MoveNext();
            }
        }
    }

Community · Accepted Answer · 2013-01-16 10:25:34Z

10

Not as good as the Linq solution, but if you want the traditional if-then style function you could write:

private static int[] Merge(int[] array1, int[] array2)
{
    var mergedArray = new int[array1.Length + array2.Length];
    int i = 0, j = 0, k = 0;
    while(k < mergedArray.Length)
    {
        if (j == array2.Length || ((i < array1.Length) && (array[i] < array2[j])))
        {
            mergedArray[k] = array1[i];
            i++;
        }
        else
        {
            mergedArray[k] = array2[j];
            j++;
        }
        k++;
    }
    return mergedArray;
}

(edit: missing brace added)

Or in English:

If array2 is empty or if there are still values in array 1 and array1[i] is less than array2[j], then take value from array1, otherwise take from array 2

Or very concise (just for fun):

private static int[] Merge(int[] array1, int[] array2)
{
    var mergedArray = new int[array1.Length + array2.Length];
    int i = 0, j = 0;
    while(i+j < mergedArray.Length)
        if (j == array2.Length || ((i < array1.Length) && (array1[i] < array2[j])))
            mergedArray[i+j] = array1[i++];
        else
            mergedArray[i+j] = array2[j++];
    return mergedArray;
}

edited Jan 16, 2013 at 10:25

CommunityBot

11 silver badge

answered Jul 11, 2012 at 20:50

nicholas

3,05724 silver badges40 bronze badges

5 Comments

d--b Over a year ago

This is much better than the Linq solution (you can measure the speed if you want). That said you must put the j == array2.Length test at the beginning of your test. ie if (j == array2.Length || ((i < array1.Length) && (array[i] < array2[j]))) otherwise, array2[j] could throw an exception

Erik Philips Over a year ago

Would this also assume that the two arrays passed in as parameters are already ordered?

jcolebrand Over a year ago

@ErikPhilips the question asker assumes so, yes

Erik Philips Over a year ago

@jcolebrand I feel like i'm blind, where did he mention the arrays are pre-sorted?

jcolebrand Over a year ago

the title How to optimize function for merging sorted arrays in C#

Erik Philips · Accepted Answer · 2012-07-11 20:47:11Z

4

Linq is your friend, here is one way:

private static int[] Merge(int[] array1, int[] array2)
{
  List<int> merged = new List<int>(array1.Length + array2.Length);
  merged.AddRange(array1);
  merged.AddRange(array2);
  return merged.GroupBy(x => x)
               .Select(x => x.Key)
               .OrderBy(x => x)
               .ToArray();
}

edited Jul 11, 2012 at 20:47

answered Jul 11, 2012 at 20:40

Erik Philips

54.9k11 gold badges133 silver badges158 bronze badges

6 Comments

BILL Over a year ago

Array.Copy(array1, newArray, array1.Length);

BILL Over a year ago

I think that arrays more faster than Lists

George Mamaladze Over a year ago

@Victor You can entirely avoid copy if you yous array1.Concat(array2) instead of merge. Linq consumes anyway 'IEnumerable' so the Concat will first enumerate through array1 and then through array2.

nemesv Over a year ago

@Victor if the two arrays can contain the same values, this solution removes the duplicates. So while your Merge(new [] {2,3,4}, new [] {4,5,6}) will results in 2,3,4,4,5,6 until Erik's solution results in 2,3,4,5,6

George Mamaladze Over a year ago

@Victor By the way is avoiding conditionals really your ultimative goal? You solution has O(n) time - with proposed Linq you will get O(n log(n)) because it involves OrderBy. Are you really happy with the trade-off?

|

Community · Accepted Answer · 2017-05-23 11:54:06Z

2

Rather than being specific to arrays, I'd suggest looking at the following question for a number of different answers for IEnumerable<T>. Most efficient algorithm for merging sorted IEnumerable<T>

The answer I provided at https://stackoverflow.com/a/14444706/184528 has only one if statement and merge multiple enumerables.

For example to use it to merge three different arrays:

    public static void Main(string[] args)
    {
        var xs = new[] { 1, 5, 9 };
        var ys = new[] { 2, 7, 8 };
        var zs = new[] { 0, 3, 4, 6 };

        foreach (var a in new [] { xs, ys, zs }.Merge())
            Console.WriteLine(a);
    }

edited May 23, 2017 at 11:54

CommunityBot

11 silver badge

answered Jan 21, 2013 at 18:32

cdiggins

18.4k7 gold badges111 silver badges107 bronze badges

Comments

Enigmativity · Accepted Answer · 2015-10-06 03:17:23Z

0

It seems to me that this is the most "reduced" version of the function:

private static int[] Merge(int[] array1, int[] array2)
{
    return array1.Concat(array2).OrderBy(x => x).ToArray();
}

It can't get much simpler than this. Not one if remaining.

I ran this Merge(new [] { 1, 2, 2, 3 }, new [] { 1, 1, 2, 4, }) on both the original code and my solution and got the same answer.

answered Oct 6, 2015 at 3:17

Enigmativity

117k12 gold badges101 silver badges184 bronze badges

Comments

John Alexiou · Accepted Answer · 2012-07-11 21:05:19Z

-1

How about using Queue<int> to drain the arrays:

    private static int[] Merge(int[] array1, int[] array2)
    {
        int N=array1.Length+array2.Length;
        Queue<int> Q1=new Queue<int>(array1);
        Queue<int> Q2=new Queue<int>(array2);
        Queue<int> result=new Queue<int>(N);

        for(int k=0; k<N; k++)
        {
            if(Q1.Count==0)
            {
                result.Enqueue(Q2.Dequeue());
            }
            else if(Q2.Count==0)
            {
                result.Enqueue(Q1.Dequeue());
            }
            else
            {
                result.Enqueue(
                    Q1.Peek()<Q2.Peek()?
                    Q1.Dequeue():
                    Q2.Dequeue());
            }
        }
        return result.ToArray();
    }

answered Jul 11, 2012 at 21:05

John Alexiou

29.4k12 gold badges83 silver badges136 bronze badges

1 Comment

George Mamaladze Over a year ago

You are copying arrays at least 3 times.

Collectives™ on Stack Overflow

How to optimize function for merging sorted arrays in C#

6 Answers 6

Comments

Or in English:

Or very concise (just for fun):

5 Comments

6 Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Or in English:

Or very concise (just for fun):

5 Comments

6 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related