# 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<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++)
for (int i = midpoint; i < input.Count; 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)
{
Left.RemoveAt(0);
}
else
{
Right.RemoveAt(0);
}
}

while (Left.Count > 0)
{
Left.RemoveAt(0);
}

while (Right.Count > 0)
{
Right.RemoveAt(0);
}

return Result;
}
}
}


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.

• Can I ask why to use IList? I'm not really sure how using an interface is better? I've never had any experience with one before Commented Sep 1, 2013 at 4:11
• @ShivamMalhotra For parameters, it means the users of your class have more choices when deciding which collection to use. For thew return type, it means you can change the returned collection without doing a breaking change. So, in both cases, it is about larger flexibility. Commented Sep 1, 2013 at 11:04

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++)
{
}

for (var i = midpoint; i < input.Count; 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)
{
left.RemoveAt(0);
}
else
{
right.RemoveAt(0);
}
}

while (left.Any())
{
left.RemoveAt(0);
}

while (right.Any())
{
right.RemoveAt(0);
}

return result;
}
}
}

• Can I ask why to use IList? I'm not really sure how using an interface is better? I've never had any experience with one before Commented Sep 1, 2013 at 4:11
• Developing to interfaces is a hallmark of object-oriented development as different implementations of that interface can be passed into your methods, or, even better, mocked versions of that interface can be used as invariants for unit testing. Commented Sep 1, 2013 at 12:39
• @ShivamMalhotra: Particularly, you can pass both List and Array and it will work equally for both. Otherwise you can't without any real reason for it. Commented Mar 2, 2015 at 5:20
• Aren't you a lot better of using indices in the merge method instead of using removeAt for everything? A removeAt is a lot more performance intensive than just incrementing an index and going from there... Commented Jun 9, 2015 at 8:01
• @ToonCasteele that's a part of the OP's code that I hadn't addressed as part of my answer. You should post an answer with a focus on performance improvements. Commented Jun 9, 2015 at 12:46

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)
{
leftIndex++;
}
else
{
rightIndex++;
}
}

while (Left.Count > leftIndex)
{