Какая тут сложность алгоритма?

[iXNomad]

Вот логи, примечания в скобках написал вручную, также выделил жирным самое важное.
Самое основное это кол-во вызовов функции bitSort (т.к. рекурсия) и количество копирований элементов массива (внутри этой функции, когда делается разбивка). Очень похоже на O(nlogn), с каждым увеличением в 10 раз происходит что-то вроде замедления роста кол-ва операций - увеличение я так понял стремится к 10, что вроде похоже на отношения логарифмов (поправьте плиз).

Elements: 10
AVG_CALLS: 23.13
AVG_COPIES: 36.01
AVG_ARRAY_COPIES: 8.97
Elements: 20 (*2 относительно 10 элементов)
AVG_CALLS: 47.56 (*2.056 относительно 10 элементов)
AVG_COPIES: 92.99 (*2.056 относительно 10 элементов)
AVG_ARRAY_COPIES: 19
Elements: 50 (*5 относительно 10 элементов)
AVG_CALLS: 121.45 (*5.25 относительно 10 элементов)
AVG_COPIES: 297.86 (*8.272 относительно 10 элементов)
AVG_ARRAY_COPIES: 49
Elements: 100 (*10 относительно 10 элементов)
AVG_CALLS: 242.41 (*10.48 относительно 10 элементов)
AVG_COPIES: 697.79 (*19.378 относительно 10 элементов) (≈10 * 2 (т.к. квадрат)?)
AVG_ARRAY_COPIES: 99
Elements: 200 (*2 относительно 100 элементов)
AVG_CALLS: 484.36 (*1.998 относительно 100 элементов)
AVG_COPIES: 1595.49 (*2,286 относительно 100 элементов)
AVG_ARRAY_COPIES: 199
Elements: 500 (*5 относительно 100 элементов)
AVG_CALLS: 1221.37 (*5.038 относительно 100 элементов)
AVG_COPIES: 4648.8 (*6.662 относительно 100 элементов)
AVG_ARRAY_COPIES: 499
Elements: 1000 (*10 относительно 100 элементов)
AVG_CALLS: 2438.75 (*10.06 относительно 100 элементов)
AVG_COPIES: 10297.5 (*14.757 относительно 100 элементов) (≈10 * 3/2 (n * отношение log_10(1000)/log_10(100))?)
AVG_ARRAY_COPIES: 999
Elements: 2000 (*2 относительно 1000 элементов)
AVG_CALLS: 4890.79 (*2.005 относительно 1000 элементов)
AVG_COPIES: 22598.5 (*2.194 относительно 1000 элементов)
AVG_ARRAY_COPIES: 1999
Elements: 5000 (*5 относительно 1000 элементов)
AVG_CALLS: 12218.2 (*5.01 относительно 1000 элементов)
AVG_COPIES: 63103 (*6.128 относительно 1000 элементов)
AVG_ARRAY_COPIES: 4999
Elements: 10000 (*10 относительно 1000 элементов)
AVG_CALLS: 24441.7 (*10.022 относительно 1000 элементов)
AVG_COPIES: 136202 (*13.227 относительно 1000 элементов) (≈10 * 4/3?)
AVG_ARRAY_COPIES: 9999
Elements: 20000 (*2 относительно 10000 элементов)
AVG_CALLS: 48865.7 (*1.999 относительно 10000 элементов)
AVG_COPIES: 292409 (*2.147 относительно 10000 элементов)
AVG_ARRAY_COPIES: 19998.9
Elements: 50000 (*5 относительно 10000 элементов)
AVG_CALLS: 122135 (*4.997 относительно 10000 элементов)
AVG_COPIES: 797100 (*5.852 относительно 10000 элементов)
AVG_ARRAY_COPIES: 49998.4
Elements: 100000 (*10 относительно 10000 элементов)
AVG_CALLS: 244296 (*9.995 относительно 10000 элементов)
AVG_COPIES: 1.6942e+06 (*12.439 относительно 10000 элементов) (≈10 * 5/4?)
AVG_ARRAY_COPIES: 99996.8 
Elements: 200000 (*2 относительно 100000)
AVG_CALLS: 488475 (*2 относительно 100000)
AVG_COPIES: 3.58843e+06 (*2.118 относительно 100000)
AVG_ARRAY_COPIES: 199989
Elements: 500000 (*5 относительно 100000)
AVG_CALLS: 1.22103e+06 (*4.998 относительно 100000)
AVG_COPIES: 9.63206e+06 (*5.685 относительно 100000)
AVG_ARRAY_COPIES: 499940
Elements: 1000000 (*10 относительно 100000)
AVG_CALLS: 2.44103e+06 (*9.992 относительно 100000)
AVG_COPIES: 2.0264e+07 (*11.96 относительно 100000) (≈10 * 6/5?)
AVG_ARRAY_COPIES: 999767

Вот код, сама сортировка в функции bitSort + две вспомогательные для получения бита и копирования массива:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TEST_DEPTH 100

void arr_cpy(int* array0, int* array1, unsigned int length);
void bitSort(int* array, unsigned int length, int element_size);
int getBit(int* number, int bit_index);

void test(int number_of_elements);

int copies;
int array_copies;
int calls;
float avg_copies = 0;
float avg_array_copies = 0;
float avg_calls = 0;

int main() {

    test(10);
    test(20);
    test(50);
    test(100);
    test(200);
    test(500);
    test(1000);
    test(2000);
    test(5000);
    test(10000);
    test(20000);
    test(50000);
    test(100000);
    test(200000);
    test(500000);
    test(1000000);

    return 0;
}

void test(int size) {

    for (int tst = 0; tst < TEST_DEPTH; tst++) {

        calls = 0;
        copies = 0;
        array_copies = 0;

        for (int i = 0; i < size; i++) {
            arr[i] = rand();
        }
        
        bitSort(arr, size, sizeof(int) * 8);

        avg_calls += (float) calls;
        avg_copies += (float) copies;
        avg_array_copies += (float) array_copies;
    }

    avg_calls /= TEST_DEPTH;
    avg_copies /= TEST_DEPTH;
    avg_array_copies /= TEST_DEPTH;

    printf("Elements: %d\nAVG_CALLS: %g\nAVG_COPIES: %g\nAVG_ARRAY_COPIES: %g\n",
            size, avg_calls, avg_copies, avg_array_copies);
    
    avg_calls = 0;
    avg_copies = 0;
    avg_array_copies = 0;
}

void bitSort(int* array, unsigned int length, int bits) {

    static int subsets = 1;
    if (subsets == length) {
        return;
    }
    static int start_length;
    calls++;
    if (calls == 1) {
        start_length = length;
        for(int j = bits-1; j >= 0; j--) {
            for(int i = 0; i < length; i++) {
                if (getBit(&(array[i]), j) == 1) {
                    bits = j + 1;
                    goto found_max;
                }
                if (j == 0) {
                    return;
                }
            }
        }
    }
found_max:;
    
    int aux_arr[length];
    int zeroes = 0;
    int ones = 0;

    for (int i = 0; i < length; i++) {
        if (getBit(&(array[i]), bits-1) == 0) {
            zeroes++;
        } else {
            ones++;
        }
    }
//    printf("Op: %d, L: %d, S: %d, B: %d, Z: %d, O: %d\n", ops, length, subsets, bits, zeroes, ones);
    bits--;
    if ((zeroes != 0) && (ones != 0)) {
        subsets++;
        int j = 0;
        int k = 0;
        for(int i = 0; i < length; i++) {
            if (getBit(&(array[i]), bits) == 0) {
                aux_arr[j] = array[i];
                j++;
            } else {
                aux_arr[zeroes+k] = array[i];
                k++;
            }
            copies++;
        }
        array_copies++;
        arr_cpy(aux_arr, array, length);
        if (length == 1 || subsets == start_length || bits == 0) {
    //        printf("OP: %d\n", ops);
            return;
        }
        bitSort(array, zeroes, bits);
        bitSort(array+zeroes, ones, bits);
    } else {
        if (length == 1 || subsets == start_length || bits == 0) {
    //        printf("OP: %d\n", ops);
            return;
        }
        bitSort(array, length, bits);
    }
}

void arr_cpy(int* arr_src, int* arr_dst, unsigned int len) {
    for(int i = 0; i < len; i++) {
        arr_dst[i] = arr_src[i];
    }
}

int getBit(int* number, int bit_index) {
   return (*number >> bit_index) % 2;
}

P.S. Я понял что скорее всего завалил рандомайзер потому что он наверное менял зерно лишь раз в секунду чего не достаточно, хотя тут это думаю не суть важно (большие тесты длились довольно долго, несколько раз точно менял зерно).