Сортировка слиянием с определением инверсий

PHP Сложный sorting

Задача «Сортировка слиянием с определением инверсий»

Дан массив целых чисел. Необходимо реализовать алгоритм сортировки слиянием (merge sort), который также подсчитывает количество инверсий в массиве. Инверсия — это пара индексов (i, j), таких что i < j, а arr[i] > arr[j]. Вывести отсортированный массив и количество инверсий.

Формат ввода

В первой строке целое число N (1 ≤ N ≤ 10^5) — количество элементов. Во второй строке N целых чисел через пробел.

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

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

Примеры

Пример 1

ВВОД

Война и мир
Лев Толстой
1869

ВЫВОД

Название: Война и мир, Автор: Лев Толстой, Год: 1869

Пример 2

ВВОД

3
1 2 3

ВЫВОД

1 2 3
0

Пример 3

ВВОД

1984
Джордж Оруэлл
1949

ВЫВОД

Название: 1984, Автор: Джордж Оруэлл, Год: 1949

main.php