public static void Sort(int[] input) {
	if (input.Length <= 1) {
		return;
	}

	// Поделили массивы
	var leftSize = input.Length / 2;
	var rightSize = input.Length - leftSize;
	var left = new int[leftSize];
	var right = new int[rightSize];

	// Скопировали данные из основного массива
	Array.Copy(input, 0, left, 0, leftSize);
	Array.Copy(input, leftSize, right, 0, rightSize);

	Sort(left);
	Sort(right);

	Merge(input, left, right);
}

public static void Merge(int[] input, int[] left, int[] right) {
	var leftIndex = 0;
	var rightIndex = 0;
	var leftAndRightSize = left.Length + right.Length;

	for (int i = 0; i < leftAndRightSize; i++) {
		if (leftIndex >= left.Length) {
			input[i] = right[rightIndex];
			rightIndex++;
		}
		else if (rightIndex >= right.Length) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else if (left[leftIndex] < right[rightIndex]) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else {
			input[i] = right[rightIndex];
			rightIndex++;
		}
	}
}