My question is what happens when qsort in C can not allocate the space it needs to do its thing. The C standard presents qsort as nonerring, but in reality it must need to allocate space for any decent algorithm.
The only truly reliable way to make qsort nonerring would be to make it fall back to a constant space algorithm if it fails to allocate what it needs. That would be terribly slow, but nonerring.
Does anyone know how this is actually handled in practice? I am most interested in how Clang and GCC handle it.
The motivation for the question is that I am working on code that needs to be extremely robust, which sorts large arrays in a setting where memory may be tight already, so I am worried about qsort putting it over the edge and not having a way in my code to manage that situation.
how Clang and GCC handle it.
It's much more fragmented in the unix world. Clang and gcc are compilers. They do not contain qsort implementation. Qsort is implemented in C standard library. See https://en.wikipedia.org/wiki/C_standard_library#Implementations .
but in reality it must need to allocate space for any decent algorithm.
But but but but quicksort can allocate memory on stack by being recursive.
how this is actually handled in practice?
code that needs to be extremely robust
I think if using glibc, keep it. It is nice. Glibc handles allocation error correctly. In contrast all recursive algorithms will just segmentation fault when there is not enough stack.
If not using glibc or going on a microcontroller, newlib is a popular choice, and it is recursive. I would roll my own qsort version and copy code from uclibc-ng, the shell sort there looks to me optimized, small and nice for a microcontroller. But I know nothing about sorting and complexities.