Median-of-medians/quickselect filter in C
Major stuff

Consider const

Design: kth_largest() has a side effect of re-arranging array. this is surprising and not part of "Finds the kth largest element of an array in O(n) time."  I'd expect code to do the job without the side effect

// long kth_largest(size_t k, long *array, size_t n_elts) {
long kth_largest(size_t k, const long *array, size_t n_elts) {


Small size error

Code may call err(1, NULL); when n_elts &lt; 5 as malloc(0) can return NULL.  I'd expect code to work for sizes 1 to 4 also.

Doubtful O() claim

"Finds the kth largest element of an array in O(n) time."    Perhaps when n >>> k, but not in general.  I'd expect O(n*k).  So perhaps

Finds the kth largest element of an array in O(n) time when k &lt;&lt;&lt; n
otherwise O(n*k)


No error check

Do not trust user input follows the rules nor allocations always succeed.

long *array = malloc(n_elts * sizeof(long));
if (array == NULL) {
  Handle_Error();
}


for (size_t i = 0; i &lt; n_elts; ++i) {
  // scanf("%ld", &amp;array[i]);
  if (scanf("%ld", &amp;array[i]) != 1) {
    Handle_Error();
  }
}




Minor stuff

object vs type

Rather than size to the type, size ot the object.  Easier to code right, review and maintain.

// qsort(a, n, sizeof(long), compare_longs);
qsort(a, n, sizeof *a, compare_longs);

// long *medians = malloc(n_sublists * sizeof(long));
long *medians = malloc(sizeof *medians * n_sublists);


No need for floating point math

i/2 will already have "floor" the quotient before the floor().  Absolutely no need for floor() and with its potential loss if precision for large i.

// return (size_t)(floor(i/2));
return i/2;


size_t is an unsigned type
Enable all warnings

pos &gt;= 0 is always true below.  A well enabled compilers would have warned.

size_t pos = -1;
...
assert(pos &gt;= 0);


Match specifier and type

"%zd" does not match a size_t.  "%zu" does.  Also implies useful warnings were not enabled.  Save time - enable warnings.  See also How to use “zd” specifier with printf()?/

// scanf("%zd", &amp;k);
// scanf("%zd", &amp;n_elts);
scanf("%zu", &amp;k);
scanf("%zu", &amp;n_elts);




Read until EOF

"I would read until EOF, but then I would have to deal with a growing array, I think." --> Yes, good idea.  Confident this is up to D. Ben Knoble abilities, so will not post code.

Design idea: pass the k as an argv[] and the array via stdin.