Merge Sort Implementation

Question

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<Node> Sort(List<Node> input)
        {
        List<Node> Result = new List<Node>();
        List<Node> Left = new List<Node>();
        List<Node> Right = new List<Node>();

        if (input.Count <= 1)
            return input;

        int midpoint = input.Count / 2;
        for (int i = 0; i < midpoint; i++)
            Left.Add(input[i]);
        for (int i = midpoint; i < input.Count; i++)
            Right.Add(input[i]);

        Left = Sort(Left); //Recursion! :o
        Right = Sort(Right);
        Result = Merge(Left, Right);

        return Result;
    }

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

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

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

        return Result;
    }
}
}

Answer 1

abstract class MergeSort

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

public static List<Node> Sort(List<Node> 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<Node> Result = new List<Node>();

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.

Answer 2

Here we go. First, the class has no need to be abstract as it has no inheritable members. In fact, since it has all static members, the class should also be static. Also followed C# naming conventions, in which local variables should be camelCased rather than the PascalCased you have. Used some LINQ to declare intent rather than implementation by using .Any() in a few places. Also re-declared List<Node> throughout as IList<Node> since programming to interfaces is better for decoupling. For that matter, wherever Node lives, may want to extract an INode interface from it and use it here. Finally, a tiny performance improvement: don't allocate the lists until after the base case has been evaluated (and returned from) so the GC doesn't have as much pressure on it.

namespace prjT02L08_Predator_Prey
{
    using System.Collections.Generic;
    using System.Linq;

    public static class MergeSort
    {
        public static IList<Node> Sort(IList<Node> input)
        {
            if (input.Count <= 1)
            {
                return input;
            }

            var midpoint = input.Count / 2;
            IList<Node> left = new List<Node>();
            IList<Node> right = new List<Node>();

            for (var i = 0; i < midpoint; i++)
            {
                left.Add(input[i]);
            }

            for (var i = midpoint; i < input.Count; i++)
            {
                right.Add(input[i]);
            }

            left = Sort(left); // Recursion! :o
            right = Sort(right);

            return Merge(left, right);
        }

        private static IList<Node> Merge(IList<Node> left, IList<Node> right)
        {
            var result = new List<Node>();

            while (left.Any() && right.Any())
            {
                if (left[0].F < right[0].F)
                {
                    result.Add(left[0]);
                    left.RemoveAt(0);
                }
                else
                {
                    result.Add(right[0]);
                    right.RemoveAt(0);
                }
            }

            while (left.Any())
            {
                result.Add(left[0]);
                left.RemoveAt(0);
            }

            while (right.Any())
            {
                result.Add(right[0]);
                right.RemoveAt(0);
            }

            return result;
        }
    }
}

Answer 3

Just focussing on your Merge method here, since I felt like using it to merge 2 Lists of objects I had, you should note that using RemoveAtis really horrible performance wise. Especially at index 0. What the list has to do in that case is move the index of every object behind that one, down by 1. This is needless and will cause your method to be really slow for big collections (easily noticable when merging 2 lists of 10 000 items or more).

Just use indices on both list and iterate through them like you would with a for loop, instead of removing each item you covered from the list:

private static List<Node> Merge(List<Node> Left, List<Node> Right)
{
    List<Node> Result = new List<Node>();
    int leftIndex = 0;
    int rightIndex = 0;
    while (Left.Count > leftIndex && Right.Count > rightIndex )
    {
        if (Left[leftIndex].F < Right[rightIndex].F)
        {
            Result.Add(Left[leftIndex]);
            leftIndex++;
        }
        else
        {
            Result.Add(Right[rightIndex]);
            rightIndex++;
        }
    }

    while (Left.Count > leftIndex)
    {
        Result.Add(Left[leftIndex]);
        leftIndex++;
    }

    while (Right.Count > rightIndex)
    {
        Result.Add(Right[rightIndex]);
        rightIndex++;
    }

    return Result;
}