Count inversions of integers read from standard input. Basic C

countInversions.c

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void *xrealloc(void *p, size_t sz)
{
        p = realloc(p, sz);
        if (p == NULL) {
                fprintf(stderr, "OOM!\n");
                exit(1);
        }
        return p;
}

int parseint(int *out)
{
        int c, n = 0;
        
        do {
                c = getchar_unlocked();
        } while (c != EOF && c < '0');
        
        if (c == EOF)
                return -1;
                
        do {
                n = 10*n + c-'0';
                c = getchar_unlocked();
        } while (c != EOF && c >= '0');
        
        *out = n;
        return 0;
}

size_t countInversions(int *tmp, int *p, size_t sz)
{
        if (sz <= 1)
                return 0;

        size_t mid = sz / 2;

        size_t count = countInversions(tmp, &p[0], mid)
                + countInversions(tmp, &p[mid], sz - mid);

        memmove(&tmp[0], &p[0], mid * sizeof p[0]);

        size_t x1 = 0;
        size_t x2 = mid;
        for (size_t fill = 0; fill < sz; fill++) {
                if (x1 < mid && (x2 == sz || tmp[x1] <= p[x2])) {
                        p[fill] = tmp[x1++];
                        count += x2 - mid;
                }
                else {
                        p[fill] = p[x2++];
                }
        }

        return count;
}

int main(void)
{
        int x;
        int *p = NULL;
        int *tmp = NULL;
        size_t num = 0;
        size_t capacity = 0;

        while (parseint(&x) != -1) {
                if (num >= capacity) {
                        capacity = capacity ? (capacity * 2) : 16;
                        p = xrealloc(p, capacity * sizeof *p);
                }
                p[num++] = x;
        }
        tmp = xrealloc(tmp, capacity * sizeof *p);

        size_t ni = countInversions(tmp, &p[0], num);

        printf("%zd\n", ni);
        return 0;
}