Testing simple radix sort implementation against qsort

radix_sort.c

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

const int MAXN = 100000;

int buf1[64][MAXN], buf2[64][MAXN], cnt[64], cnt2[64];
long long used;

// za brojeve do 262144
void radix_sort(int *a, int *b)
{
    int t;
    long long used = 0;
    for (int *i = a; i < b; ++i)
    {
        t = *i & 63;
        buf1[t][cnt[t]++] = *i;

        used |= 1LL << t;
    }

    // ispis 1
    // for (int i = 63 - __builtin_clzll(used);
    //      used != 0;
    //      i = 63 - __builtin_clzll(used))
    // {
    //     printf("%d\n", i);
    //     for (int j = 0; j < cnt[i]; ++j)
    //         printf(" %d\n", buf1[i][j]);

    //     used &= ~(1LL << i);
    // }

    memset(cnt2, 0, sizeof(cnt2)); // ne treba, ali nek stoji
    long long used2 = 0;

    for (int i = 63 - __builtin_clzll(used);
         used != 0;
         i = 63 - __builtin_clzll(used))
    {

        for (int j = 0; j < cnt[i]; ++j)
        {
            int t = (buf1[i][j] >> 6) & 63;
            buf2[t][cnt2[t]++] = buf1[i][j];

            used2 |= 1LL << t;
        }

        used &= ~(1LL << i);
    }

    // ispis 2
    // for (int i = 63 - __builtin_clzll(used2);
    //      used2 != 0;
    //      i = 63 - __builtin_clzll(used2))
    // {
    //     printf("%d\n", i);
    //     for (int j = 0; j < cnt2[i]; ++j)
    //         printf(" %d\n", buf2[i][j]);

    //     used2 &= ~(1LL << i);
    // }

    memset(cnt, 0, sizeof(cnt)); // TODO: ubrzati, mora biti način
    used = 0;

    for (int i = 63 - __builtin_clzll(used2);
         used2 != 0;
         i = 63 - __builtin_clzll(used2))
    {
        for (int j = 0; j < cnt2[i]; ++j)
        {
            int t = (buf2[i][j] >> 12) & 63;
            buf1[t][cnt[t]++] = buf2[i][j];

            used |= 1LL << t;
        }

        used2 &= ~(1LL << i);
    }

    --b;
    for (int i = 63 - __builtin_clzll(used);
         used != 0;
         i = 63 - __builtin_clzll(used))
    {
        for (int j = 0; j < cnt[i]; ++j)
            *b-- = buf1[i][j];

        used &= ~(1LL << i);
    }
}

int n;
int a[1000005], b[1000005];

int cmpfunc(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int main(int argc, char *argv[])
{
    srand(time(NULL));

    n = atoi(argv[1]);

    for (int i = 0; i < n; ++i)
    {
        a[i] = rand() % 200000;
        b[i] = a[i];
    }

    // for (int i = 0; i < 10; ++i)
    //     printf("%d ", a[i]);
    // printf("\n");

    clock_t begin, end;
    double difference;
    begin = clock();

    radix_sort(a, a + n);

    end = clock();

    difference = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("radix: %lf\n", difference);

    begin = clock();

    qsort(b, n, sizeof(int), cmpfunc);

    end = clock();

    difference = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("qsort: %lf\n", difference);

    for (int i = 1; i < n; ++i)
        if (!(a[i - 1] <= a[i]))
            printf("KRIVO %d\n", i);

    // for (int i = 0; i < 10; ++i)
    //     printf("%d ", a[i]);
    // printf("\n");

    // for (int i = 0; i < 4; ++i)
    // {
    //     printf("%d ", a[i]);
    // }
    // printf("\n");

    return 0;
}

// plot here: https://imgur.com/Z0PqqUN
// import subprocess
// import matplotlib.pyplot as plt
// from tqdm import tqdm

// if __name__ == "__main__":

//     radix, qsort = [], []

//     for x in tqdm(range(100, 100005, 100)):
//         test = subprocess.Popen(["./a.out", str(x)], stdout=subprocess.PIPE)

//         output = str(test.communicate()[0]).replace("\\n",  " ")

//         radix.append(float(output.split()[1]))
//         qsort.append(float(output.split()[3]))

//         # print(output.split()[1],
//         #       output.split()[3])

//     r = list(range(100, 100005, 100))

//     plt.plot(r, radix, "-b", label="Radix")
//     plt.plot(r, qsort, "-r", label="QSort")
//     plt.ylabel('qsort vs radix')
//     plt.legend(loc="upper left")
//     plt.savefig("plot.png")