How to refactor this routine to avoid the use of recursion?

Question

So I was writing a mergesort in C# as an exercise and although it worked, looking back at the code, there was room for improvement.

Basically, the second part of the algorithm requires a routine to merge two sorted lists.

Here is my way too long implementation that could use some refactoring:

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    if (sLeft.Count == 0 || sRight.Count == 0)
    {
        sLeft.AddRange(sRight);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count == 1)
    {
        if (sLeft[0] <= sRight[0])
            sLeft.Add(sRight[0]);
        else
            sLeft.Insert(0, sRight[0]);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count > 1)
    {
        for (int i=0; i<sRight.Count; i++)
        {
            if (sLeft[0] <= sRight[i])
            {
                sRight.Insert(i, sLeft[0]);
                return sRight;
            }
        }
        sRight.Add(sLeft[0]);
        return sRight;
    }
    else if (sLeft.Count > 1 && sRight.Count == 1)
    {
        for (int i=0; i<sLeft.Count; i++)
        {
            if (sRight[0] <= sLeft[i])
            {
                sLeft.Insert(i, sRight[0]);
                return sLeft;
            }
        }
        sLeft.Add(sRight[0]);
        return sLeft;
    }
    else
    {
        List<int> list = new List<int>();
        if (sLeft[0] <= sRight[0])
        {
            list.Add(sLeft[0]);
            sLeft.RemoveAt(0);
        }
        else
        {
            list.Add(sRight[0]);
            sRight.RemoveAt(0);
        }

        list.AddRange(MergeSortedLists(sLeft, sRight));
        return list;
    }       
}

Surely this routine can be improved/shortened by removing recursion, etc. There are even other ways to merge 2 sorted lists. So any refactoring is welcome.

Although I do have an answer, I'm curious as to how would other programmers would go about improving this routine.

Thank you!

Answer 1

Merging two sorted lists can be done in O(n).

List<int> lList, rList, resultList;
int r,l = 0;

while(l < lList.Count && r < rList.Count)
{
  if(lList[l] < rList[r]
    resultList.Add(lList[l++]);
  else
    resultList.Add(rList[r++]);
}
//And add the missing parts.
while(l < lList.Count)
  resultList.Add(lList[l++]);
while(r < rList.Count)
  resultList.Add(rList[r++]);

Answer 2

My take on this would be:

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    List<int> result = new List<int>();
    int indexLeft = 0;
    int indexRight = 0;

    while (indexLeft < sLeft.Count || indexRight < sRight.Count)
    {
        if (indexRight == sRight.Count ||
            (indexLeft < sLeft.Count && sLeft[indexLeft] < sRight[indexRight]))
        {
            result.Add(sLeft[indexLeft]);
            indexLeft++;
        }
        else
        {
            result.Add(sRight[indexRight]);
            indexRight++;
        }
    }
    return result;
}

Exactly what I'd do if I had to do it by hand. =)