std::sort algorithms memory usage

Question

I'm wondering whether the standard libraries sorting algorithms (e.g. std::sort) are using the heap memory for sorting.

Is there any reliable source how to find out what kind (heap, stack) and how much of temporary memory is used by a sorting algorithm or any standard library algorithm in general?

The background is that I consider to introduce some of the standard library algorithms into an embedded environment in which a controlled memory usage is crucial. (especially the heap shall not be used).

Thank you in advance!

Answer 1

What memory the standard library algorithms can use is not mandated by the standard, so the implementation can generally do as it wants. That includes allocating heap memory.

You can check if some specific implementation provides the guarantees you want, but again, in general, you have no control over how the implementation implements its algorithms.

---

However:

The background is that I consider to introduce some of the standard library algorithms into an embedded environment in which a controlled memory usage is crucial. (especially the heap shall not be used).

The implementation must make sure that its algorithms do what they are supposed to do as defined by the standards. That means: If you have a C++ compiler that supports your target environment, it must do the right thing on said target platform, however it achieves that.

In particular: If your platform does not have a heap, any implementation that supports it must not use the heap.