Merge Sort Implementation

Any reviews/ways to speed up/general improvements for my Merge Sort? Maybe something to simplify it or add more to it?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace prjT02L08_Predator_Prey
{
    abstract class MergeSort
    {
        public static List Sort(List input)
        {
        List Result = new List();
        List Left = new List();
        List Right = new List();

        if (input.Count  Merge(List Left, List Right)
    {
        List Result = new List();
        while (Left.Count > 0 && Right.Count > 0)
        {
            if (Left[0].F  0)
        {
            Result.Add(Left[0]);
            Left.RemoveAt(0);
        }

        while (Right.Count > 0)
        {
            Result.Add(Right[0]);
            Right.RemoveAt(0);
        }

        return Result;
    }
}
}

abstract class MergeSort

This class shouldn't be abstract, it should be static.

public static List Sort(List input)

Why does the method require List? Wouldn't it be better if it accepted any IList (or IReadOnlyList if you're on .Net 4.5)? Also, it would make sense to make your code generic, so that it would work on types other than Node.

List Result = new List();

The usual convention in C# is to name local variables in camelCase, not PascalCase.

return input;

Returning the input might be unexpected. If you don't want to change it, you should clearly document it.

Left.RemoveAt(0);

This is very inefficient operation for a List. Either use a collection that can do this efficiently (like LinkedList or Queue) or, even better, just use indexes instead of modifying the collection.

Your code also does a lot of copying and creating new lists. That's good for readability, but if you want your code to be fast, you need just two lists that you can modify.

You would need to work with sublists (list, start index, length), not whole lists. First, merge the 1-element sublists from list A to list B, then merge the 2-element sublists from B to A, etc.

Also, another optimization is not to start with 1-element sublists, but take advantage of the fast that there are likely to be some sorted sublists in the input already. This is especially effective if the input is already sorted (or mostly sorted). But I think it wouldn't work with your recursive approach.

StackExchange Code Review Q#30545, answer score: 5