Implementation violates stated preallocation-all-memory-at-construction-time guarantees

[gsauthof]

In the header it's stated:

In particular it provides mechanisms to preallocate all memory 
at construction time.

tdigestc/go/tdigest.h

Lines 11 to 12 in a2a61e6

	// It focuses on being in portable C that should be easy to integrate into other
	// languages. In particular it provides mechanisms to preallocate all memory

However, each invocation of td_add() may invoke merge() which in turn calls qsort().
According to the C standard, a qsort implementation is free to dynamically allocate additional memory during sorting.

At least the GNU libc does indeed allocate additional heap memory for some input sizes.

FWIW, I observed such allocations under RHEL8 when using a tdigest compression of 100 and when such allocations occur, they add extra latency to an td_add() call in the order of magnitude of 50 µs, whereas a 'normal' td_add() just has an overhead of 10 ns or so.

---

A fix for this may be to switch to std::sort().

However, tdigest might profit from stable sorting, and then you might want to switch to an sort algorithm that sorts inplace (or just needs constant scratch space that can be pre-allocated, as well) and is stable.