Помогите решить задачу.
В этой задаче вам необходимо проанализировать некоторый алгоритм сортировки. Этот алгоритм сортирует последовательность из N различных целых чисел, переставляя по два соседних элемента последовательности до тех пор, пока она не будет упорядочена по возрастанию. Ваша задача состоит в том, чтобы посчитать, сколько таких перестановок двух соседних элементов необходимо сделать, чтобы отсортировать заданную последовательность.
Входные данные
Первая строка входных данных содержит единственное натуральное число 1 ≤ N < 500000 - длину сортируемой последовательности. Каждая из последующих N строк содержит целое число 0 ≤ a[i] ≤ 999999999, i-ый элемент последовательности. Все элементы последовательности различны.
Выходные данные
Выведите единственное целое число - минимальное количество перестановок соседних элементов последовательности, необходимое для того, чтобы отсортировать ее по возрастанию.
Преподаватель сказал использовать не пузырьковую сортировку, а сортировку слиянием. Я нашёл код сортировки слиянием, но при массивах в 200000 элементов и более происходило переполнение стека. Как реализовать таую сортировку для больших массивов? Как подсчитать количество перестановок?
Программа выглядит так.
#include <stdio.h>
int main() {
int a[100], N, pr = 0, i, j, c;
scanf("%d", &N);
for(i = 0; i < N; i++) {
scanf("%d", &a[i]);
printf("\n");
}
for(i = 0; i < N; i++)
for(j = N - 2; j >= i; j--) {
if(a[j] > a[j + 1]) {
c = a[j];
a[j] = a[j + 1];
a[j + 1] = c;
pr++;
}
}
printf("%d\n", pr);
return 0;
}
Но преподаватель сказал, что нельзя использовать пузырькоую сортировку, а нужно использовать сортировку слиянием. Я находил много таких алгоритмов, но с их помощью нельзя отсортировать массив размером более 200000 элементов. Иными словами, нужен алгоритм с глобальными переменными. Покажите такой код, который бы сортировал большие массивы и чтобы можно было пересчитывать количество перестановок.
