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++;
        }
    }
}

Take a look at `MergeOrdered` method [here](http://stackoverflow.com/questions/37726664/how-to-merge-2-text-files/37732758#37732758) — Ivan Stoev, Jun 13 '16 at 01:31

Tim Biegeleisen · Answer 1 · 2016-06-13T06:39:52.183

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.

In for loops I get error for index 1 and 2 : only assignment call increment decrement — Alex, Jun 13 '16 at 06:38
yes this fixed the problem. But I get nullreferenceexception at FinalDeliverables.Add(a[index1]); Any idea ? — Alex, Jun 13 '16 at 07:32
On which line does this exception occur? What is the sample data you are using for `a` and `b` ? — Tim Biegeleisen, Jun 13 '16 at 07:34
This should not be happening AFAIK. If you can debug your code and let me know the state of `a` and `b` then maybe I can help you further. If you can access `a[index1].ID` then I see no reason why you can not add `a[index1]` to the list. — Tim Biegeleisen, Jun 13 '16 at 07:40
I am passing list a and list b , same of type Deliverable class. Deliveralbe holds id weight and some other parameters. — Alex, Jun 13 '16 at 07:43
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/114502/discussion-between-tim-biegeleisen-and-alex). — Tim Biegeleisen, Jun 13 '16 at 07:44

sujith karivelil · Answer 2 · 2016-06-13T01:29:14.333

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]);
        }
    }
}

Merging two lists which are already sorted in c#

2 Answers2