Merging two lists into one and sorting the items

Question

Is there a way to merge(union without dupes) two given lists into one and store the items in sorted way by using ONE for loop?

Also, i am looking for a solution which does not makes use of API methods ( like, union, sort etc).

Sample Code.

private static void MergeAndOrder() 
{
var listOne = new List<int> {3, 4, 1, 2, 7, 6, 9, 11}; 
var listTwo = new List<int> {1, 7, 8, 3, 5, 10, 15, 12}; 

//Without Using C# helper methods...
//ToDo.............................

//Using C# APi.
var expectedResult = listOne.Union(listTwo).ToList(); 
expectedResult.Sort();//Output: 1,2,3,4,5,6,7,8,9,10,11,12,15
//I need the same result without using API methods, and that too by iterating over items only once.


}

PS: I have been asked this question in an interview, but couldn't find answer as yet.

Answer 1

Why can't you use the api methods? Re-inventing the wheel is dumb. Also, it's the .ToList() call that's killing you. Never call .ToList() or .ToArray() until you absolutely have to, because they break your lazy evaluation.

Do it like this and you'll enumerate the lists with the minimum amount necessary:

var expectedResult = listOne.Union(listTwo).OrderBy(i => i);

This will do the union in one loop using a hashset, and lazy execution means the base-pass for the sort will piggyback on the union. But I don't think it's possible finish the sort in a single iteration, because sorting is not a O(n) operation.

Answer 2

Without the precondition that both lists are sorted before the merge + sort operation, you can't do this in O(n) time (or "using one loop").

Add that precondition and the problem is very easy.

Keep two iterators, one for each list. On each loop, compare the element from each list and choose the smaller. Increment that list's iterator. If the element you are about to insert in the final list is already the last element in that list, skip the insert.

In pseudocode:

List a = { 1, 3, 5, 7, 9 }
List b = { 2, 4, 6, 8, 10 }
List result = { }
int i=0, j=0, lastIndex=0
while(i < a.length || j < b.length)
    // If we're done with a, just gobble up b (but don't add duplicates)
    if(i >= a.length)
        if(result[lastIndex] != b[j])
            result[++lastIndex] = b[j]
        j++
        continue

    // If we're done with b, just gobble up a (but don't add duplicates)
    if(j >= b.length)
        if(result[lastIndex] != a[i])
            result[++lastIndex] = a[i]
        i++
        continue

    int smallestVal

    // Choose the smaller of a or b
    if(a[i] < b[j])
        smallestVal = a[i++]
    else
        smallestVal = b[j++]

    // Don't insert duplicates
    if(result[lastIndex] != smallestVal)
        result[++lastIndex] = smallestVal
end while