using System;
public class HelloWorld
{
public static void Main()
{
int[] arr = new int[] { 8, 1, 6, 7, 2, 6, 9, 4 };
MergeSort(arr, 0, arr.Length-1);
foreach (int i in arr)
{
Console.Write(i + " ");
}
}
public static void MergeSort(int[] array, int left, int right)
{
if (left >= right) return;
int middle = (left + right) / 2;
MergeSort(array, left, middle);
MergeSort(array, middle + 1, right);
Merge(array, left, middle, right);
}
public static void Merge(int[] array, int left, int middle, int right)
{
int[] temp = new int[right - left + 1];
int index = 0, lindex = left, rindex = middle + 1;
while (lindex <= middle && rindex <= right)
{
if (array[rindex] < array[lindex])
{
temp[index++] = array[rindex++];
}
else
{
temp[index++] = array[lindex++];
}
}
while (lindex <= middle)
{
temp[index++] = array[lindex++];
}
while (rindex <= right)
{
temp[index++] = array[rindex++];
}
while (--index >= 0)
{
array[left + index] = temp[index];
}
}
}