Сортировка по чётности и значению

Java Средний sorting

Задача «Сортировка по чётности и значению»

Дан массив целых чисел. Необходимо отсортировать его таким образом, чтобы сначала шли все чётные числа в порядке возрастания, а затем все нечётные числа в порядке убывания. Если число равно 0, оно считается чётным. Реализуйте сортировку без использования встроенных методов сортировки, используя алгоритм сортировки слиянием (merge sort). Дополнительно, после сортировки выведите количество перестановок, выполненных при сортировке (т.е. количество обменов элементов).

Формат ввода

Первая строка содержит целое число N (1 ≤ N ≤ 1000) — количество элементов в массиве. Вторая строка содержит N целых чисел, разделённых пробелами — элементы массива.

Формат вывода

Выведите отсортированный массив в одну строку через пробел. Затем на следующей строке выведите одно целое число — количество выполненных обменов.

Примеры

Пример 1

ВВОД

4
0 7 2 9

ВЫВОД

0 2 9 7
2

Пример 2

ВВОД

6
6 5 4 3 2 1

ВЫВОД

2 4 6 5 3 1
5

main.java