using System;
class MainClass {
static void Main() {
int[] numbers = {99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0};
//6, 8, 7
//6, 8, 8
Console.WriteLine(ToString(numbers));
numbers = MergeSort(numbers);
Console.WriteLine(ToString(numbers));
}
public static int[] MergeSort(int[] array) {
if (array.Length == 1) {
return array;
}
// Split Array into right and left
int[] left = new int[array.Length / 2];
int[] right = new int[array.Length - array.Length / 2];
for (int i = 0; i < array.Length; i++) {
if (i < array.Length / 2) {
left[i] = array[i];
} else {
right[i - array.Length / 2] = array[i];
}
}
return Merge(MergeSort(left), MergeSort(right));
}
public static int[] Merge(int[] left, int[] right) {
int[] merged = new int[left.Length + right.Length];
int index = 0;
int leftIndex = 0;
int rightIndex = 0;
while (leftIndex < left.Length || rightIndex < right.Length) {
if (leftIndex == left.Length) {
merged[index++] = right[rightIndex++];
} else if (rightIndex == right.Length) {
merged[index++] = left[leftIndex++];
} else {
if (left[leftIndex] < right[rightIndex]) {
merged[index++] = left[leftIndex++];
} else {
merged[index++] = right[rightIndex++];
}
}
}
return merged;
}
public static string ToString(int[] array) {
string s = "{";
for (int i = 0; i < array.Length; i++) {
if (i > 0) {
s += ", ";
}
s += array[i];
}
s += "}";
return s;
}
}
