Merging two lists which are already sorted in c#

Question

So i have two sorted lists with deliverable's and I want to Merge them. I never did this operation before and i can not really make it work. You can see method below that i wrote. I can not figure out while statement because it fires exception all the time. I dont know what to do...

public void MergeLists(List<Deliverable> a, List<Deliverable> b)
{
    int index1 = 0;
    int index2 = 0;

    while (a.Count() >= index1 || b.Count() >= index2)
    {
        if (a[index1].ID> b[index2].ID)
        {
            FinalDeliverables.Add(a[index1]);
            index1++;
        }
        else if (a[index1].ID < b[index2].ID)
        {
            FinalDeliverables.Add(a[index2]);
            index2++;
        }
        else if (a[index1].ID == b[index2].ID)
        {
            FinalDeliverables.Add(a[index1]);
            FinalDeliverables.Add(a[index2]);
            index1++;
            index2++;
        }
    }
}

Answer 1

I believe that the exceptions you are getting are coming from null pointers. This would occur if, for example, you already reached the end of one of the lists, yet your while loop is still trying to compare values. One workaround to this is to simply add a check before the if statements to see if one (or both) of the ends of the lists have been reached. If so, then simply add the remainder of the items from the other list.

public void MergeLists(List<Deliverable> a, List<Deliverable> b)
{
    int index1 = 0;
    int index2 = 0;

    while (true)
    {
        // if the end of the 'a' list has been reached, then add
        // everything from the 'b' list and break from the loop
        if (index1 >= a.Count()) {
            for (int i=index2; i < b.Count(); ++i) {
                FinalDeliverables.Add(b[i]);
            }
            break;
        }

        // if the end of the 'b' list has been reached, then add
        // everything from the 'a' list and break from the loop
        if (index2 >= b.Count()) {
            for (int i=index1; i < a.Count(); ++i) {
                FinalDeliverables.Add(a[i]);
            }
            break;
        }
        if (a[index1].ID > b[index2].ID)
        {
            FinalDeliverables.Add(a[index1]);
            index1++;
        }
        else if (a[index1].ID < b[index2].ID)
        {
            FinalDeliverables.Add(a[index2]);
            index2++;
        }
        else if (a[index1].ID == b[index2].ID)
        {
            FinalDeliverables.Add(a[index1]);
            FinalDeliverables.Add(a[index2]);

            index1++;
            index2++;
        }
    }
}

Note that a side effect of this refactor is that your original while loop no longer has to check boundaries. Instead, the loop will be terminated when one of the lists has been exhausted.

Also note that this solution assumes that your input lists are sorted in descending order.

Answer 2

You can use the LINQ Extension methods for this purpose, The Method signature for MergeLists will be like the following:

public void MergeLists(List<Deliverable> a, List<Deliverable> b) 
{
    var finalList = a.Concat(b);
    List<Deliverable> FinalSortedList = finalList.OrderBy(x => x.ID).ToList();
}

Or else you can modify your own method as like the following: Before that Let me assume the following, The Count of elements in the Input list a will always be Greater than that of b. SO what you need to do is Check the count of elements before calling the method as well. So the call will be like the following:

if(a.Count>b.Count)
   MergeLists(a,b);
else
   MergeLists(b,a);

You mentioned that the two inputs ware sorted, Let me assume those lists are sorted in ascending order. Now consider the following code:

public void MergeLists(List<Deliverable> a, List<Deliverable> b)
{
    int largeArrayCount = a.Count;
    int currentBIndex = 0;
    List<Deliverable> FinalResult = new List<Deliverable>();
    for (int i = 0; i < largeArrayCount; i++)
    {
        if (i < b.Count)
        {
            if (a[i].ID >= b[i].ID)
            {
                // Add All elements of B Which is smaller than current element of A
                while (a[i].ID <= b[currentBIndex].ID)
                {
                    FinalResult.Add(b[currentBIndex++]);
                }
            }
            else
            {
                FinalResult.Add(a[i]);
            }
        }
        else
        {
            // No more elements in b so no need for checking
            FinalResult.Add(a[i]);
        }
    }
}