Its been years (10+) since I have worked with sorting algorithms directly. So I have been trying to go over them again to refresh my memory. The thing is my ideas of how to do it doesn't seam to match the way I have the tutorials doing it.
Does it matter? Assuming that my code is working I would almost mean that its correct. However I have also been looking into the Big-O I really cant remember ever seeing this before. I would almost think that if you code it incorrectly it will slow things down and mess up the performance.
public class MergeSort2
{
public MergeSort2()
{
var data = Util.CreateData.CreateRandomIntArray(200); // just a method that spits out an array of ints
var sortedData = Sort(data);
}
private int[] copyArray(int[] A, int start, int end)
{
int[] result = new int[end-start];
int cnt = 0;
for (int i = start; i < end; i++)
{
result[cnt] = A[i];
cnt++;
}
return result;
}
public int[] Sort(int[] data)
{
if (data.Length <= 1)
return data;
var length = data.Length / 2;
int[] LeftArray = copyArray(data,0,length);
int[] RightArray = copyArray(data, length,data.Length);
Array.ForEach(data, a => Console.Write(a + ","));
Console.Write("\r\n");
Array.ForEach(LeftArray, a => Console.Write(a + ","));
Console.Write("\t - \t");
Array.ForEach(RightArray, a => Console.Write(a + ","));
Console.Write("\r\n");
RightArray = Sort(RightArray);
LeftArray = Sort(LeftArray);
var sorted = merge(RightArray, LeftArray);
Console.Write("Sorted: ");
Array.ForEach(sorted, a => Console.Write(a + ","));
Console.Write("\r\n");
return sorted;
}
public int[] merge(int[] right, int[] left)
{
int[] merged = new int[right.Length + left.Length];
int cntright = 0;
int cntleft = 0;
for (int i = 0; i < merged.Length; i++)
{
if (cntright == right.Length)
{
merged[i] = left[cntleft];
cntleft++;
}
else if (cntleft == left.Length)
{
merged[i] = right[cntright];
cntright++;
}
else if (right[cntright] <= left[cntleft])
{
merged[i] = right[cntright];
cntright++;
}
else
{
merged[i] = left[cntleft];
cntleft++;
}
}
return merged;
}
}
So I guess my question is two fold:
- How is my implementation of merge sort?
- Does it matter that I'm implementation isn't exactly the same as everyone else?