Для задания мы должны написать функцию сортировки слиянием на C:
sort(int* array, unsigned len);
У меня есть код, написанный и работающий, но его время выполнения O(N^2*log[N]), что противоречит цели сортировки слиянием. Причина неэффективности заключается в том, что часть слияния выглядит следующим образом:
while(ct1 < len1 && ct2 < len2){
if(array[0] < array[len1 - ct1]){
ct1++;
array++; // no longer look at that element
}
else{
int position = len1 - ct1;
int hold = array[position];
while(position > 0){
array[position] = array[position - 1];
position--;
}
array[0] = hold;
ct2++;
array++;
}
}
где ct1 — счетчик для левого списка, ct2 — счетчик для правого списка, а массив — указатель на массив. И ct1, и ct2 изначально установлены равными нулю. Как я уже сказал, это работает, просто неэффективно, потому что приходится все перекладывать. Я хотел разбить вложенные массивы на два временных массива перед сортировкой, но вы якобы не можете создавать массивы, длина которых не определена как константы. Также должен отметить, что хотя я могу использовать вспомогательные функции, я не могу изменить параметры функции: должен быть указатель на массив и длина.
