Having some issues getting my Merge Sort to work. If anyone can help me with it, I'd appreciate it.
I'm not sure why, but the list that comes out of the sort isn't sorted. I've tried using breakpoints, but that doesn't seem to help find the issue.
static class MergeSort
{
//Sort<T> - The <T> is called a generic parameter
public static IList<T> Sort<T>(IList<T> input)
{
List<T> Result = new List<T>();
Queue<T> Left = new Queue<T>(); //Switched from lists to queues because removing at index 0 is more efficient
Queue<T> Right = new Queue<T>();
//Dequeue() and Count() have a time complexity of O(1)
if (input.Count <= 1)
return input;
int midpoint = input.Count / 2;
for (int i = 0; i < midpoint; i++)
Left.Enqueue(input[i]);
for (int i = midpoint; i < input.Count; i++)
Right.Enqueue(input[i]);
Left = new Queue<T>(Sort(Left.ToList())); //Recursion! :o
Right = new Queue<T>(Sort(Right.ToList())); ; //This line and the one above split the list into smaller lists (left and right)
Result = Merge(Left, Right); //This joins the lists together
return Result;
}
private static List<T> Merge<T>(Queue<T> Left, Queue<T> Right)
{
List<T> Result = new List<T>();
while (Left.Count /* O(1) operation */ > 0 && Right.Count > 0)
{
int cmp = Comparison((Left.Peek() as Entity), (Right.Peek() as Entity));
//If cmp is less than 0, left is less. If it is greater, left is greater
if (cmp < 0)
Result.Add(Left.Dequeue());
//Left.RemoveAt(0) - Using a list to remove at a certain point is inefficient
else
Result.Add(Right.Dequeue());
}
while (Left.Count > 0)
Result.Add(Left.Dequeue());
while (Right.Count > 0)
Result.Add(Right.Dequeue());
return Result;
}
private static int Comparison(Entity Left, Entity Right)
{
if (Left.TimesEaten > Right.TimesEaten)
{
return 1;
}
else
{
return -1;
}
}
}
If you need to know, in the method "Comparison", Left.TimesEaten is an integer.
You have a bug in the Merge
implementation. For a given pair of Left
and Right
queues, you are comparing just their first element. You actually need to re-perform the comparison after each addition (for example, by moving the Comparison
call inside your loop):
private static List<T> Merge<T>(Queue<T> Left, Queue<T> Right)
{
List<T> Result = new List<T>();
while (Left.Count > 0 && Right.Count > 0)
{
int cmp = Comparison((Left.Peek() as Entity), (Right.Peek() as Entity));
//If cmp is less than 0, left is less. If it is greater, left is greater
if (cmp < 0)
Result.Add(Left.Dequeue());
else
Result.Add(Right.Dequeue());
}
// ...