How is a qsort allocation failure handled?

Question

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.

Answer 1

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?

where	how	link
BSD libc	recursive	https://github.com/freebsd/freebsd-src/blob/83507f9e6fedbc02d1acecc9fb5c09eae34b1ae6/sys/libkern/qsort.c#L194
Glibc	uses heapsort in case of allocation error	https://github.com/bminor/glibc/blob/master/stdlib/qsort.c#L413
Microsoft MSVCRT	mystery
Microsoft UCRT	more mystery
dietlibc	recursive	https://github.com/ensc/dietlibc/blob/7d1eb8beb7cdaaa1c5bc010896c9f70cdb7b2519/lib/qsort.c#L56
uclibc-ng	uses shell sort	https://github.com/wbx-github/uclibc-ng/blob/6b06704d35f43a019ce3bd3d2221aef3d8e2cba3/libc/stdlib/stdlib.c#L705 it is based on https://www.stjarnhimlen.se/snippets/strsort.c|
newlib	recursive (with optimization)	https://github.com/bminor/newlib/blob/master/newlib/libc/search/qsort.c#L327 , see https://github.com/bminor/newlib/blob/master/newlib/libc/search/qsort.c#L149
klibc	uses comb sort	https://github.com/brainflux/klibc/blob/master/usr/klibc/qsort.c
musl	recursive, uses smooth sort	https://github.com/kraj/musl/blob/kraj/master/src/stdlib/qsort.c#L200
bionic	recursive	https://github.com/aosp-mirror/platform_bionic/blob/main/libc/upstream-freebsd/lib/libc/stdlib/qsort.c#L194
picolibc	copied from newlib
gnulib	allocates constant memory on stack up front for array up to SIZE_MAX in size	https://github.com/coreutils/gnulib/blob/master/lib/qsort.c#L98
reactos	recursive	https://github.com/mirror/reactos/blob/master/reactos/lib/sdk/crt/stdlib/qsort.c#L157

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.