using System;
public class MergeSort {
public static void Sort (int[] data, int left, int right) {
if (left < right) {
int middle = (left + right)/2;
Sort(data, left, middle);
Sort(data, middle + 1, right);
Merge(data,left, middle, middle+1, right);
}
}
public static void Merge(int[] data, int left, int middle, int middle1, int right) {
int oldPosition = left;
int size = right - left + 1;
int[] temp = new int[size];
int i = 0;
while (left <= middle && middle1 <= right) {
if (data[left] <= data[middle1])
temp[i++] = data[left++];
else
temp[i++] = data[middle1++];
}
if (left > middle)
for (int j = middle1; j <= right; j++)
temp[i++] = data[middle1++];
else
for (int j = left; j <= middle; j++)
temp[i++] = data[left++];
Array.Copy(temp, 0, data, oldPosition, size);
}
public static void Main (String[] args) {
int[] data = new int[]{2,3,1,6,2,98,4,6,4,3,45};
for (int i = 0; i < data.Length; i++) {
Console.WriteLine(data[i]);
}
Sort(data, 0, data.Length-1);
for (int i = 0; i < data.Length; i++) {
Console.WriteLine(data[i]);
}
}
}