To keep it short. I made a MergeSort, which should sort an int[]
. To test the MergeSort I made an array containing 4 integers
in random order. It returns the exact list in the order given to the MergeSort, instead of doing what it should do. I wonder what I did wrong.
Edit: The first two merges return these two lists: 4, 15 && 5, 16, however the last merge doesn't work.
This is the actual code:
public static int[] Merge(int[] list, int left, int mid, int right)
{
int[] returnList = new int[list.Length];
int Index = left;
//last value of left half
int leftEnd = mid;
//both the left side and right side contain atleast one value
while (leftEnd >= left && right >= (mid + 1))
{
if (list[left] <= list[(mid + 1)])
{
returnList[Index] = list[left];
left++;
}
else
{
returnList[Index] = list[(mid + 1)];
mid++;
}
Index++;
}
//right side is empty, left contains atleast one value
while (leftEnd >= left)
{
returnList[Index] = list[left];
left++;
Index++;
}
//left side is empty, right contains atleast one value
while (right >= (mid + 1))
{
returnList[Index] = list[(mid + 1)];
mid++;
Index++;
}
return returnList;
}
public static int[] Split(int[] list, int left, int right)
{
if (right > left)
{
int mid = (right + left) / 2;
Split(list, left, mid); //first half
Split(list, (mid + 1), right); //second half
list = Merge(list, left, (mid + 1), right);
}
return list;
}
My Main:
int[] intArray = new int[] { 12, 4, 16, 5 };
int[] ReturnTest = MergeSort.Split(intArray, 0, intArray.Length - 1);
foreach (int value in ReturnTest)
{
Console.WriteLine(value);
}
The expected output: 4, 5, 12, 16
The actual output: 12, 4, 16, 5