Adjust the testing approach to start from scenarios with only 2
elements, as insertion sort no longer handles such cases.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
The mergesort removal from qsort implementation (commit 03bf8357e8)
had the side-effect of making sorting nonstable. Although neither
POSIX nor C standard specify that qsort should be stable, it seems
that it has become an instance of Hyrum's law where multiple programs
expect it.
Also, the resulting introsort implementation is not faster than
the previous mergesort (which makes the change even less appealing).
This patch restores the previous mergesort implementation, with the
exception of machinery that checks the resulting allocation against
the _SC_PHYS_PAGES (it only adds complexity and the heuristic not
always make sense depending on the system configuration and load).
The alloca usage was replaced with a fixed-size buffer.
For the fallback mechanism, the implementation uses heapsort. It is
simpler than quicksort, and it does not suffer from adversarial
inputs. With memory overcommit, it should be rarely triggered.
The drawback is mergesort requires O(n) extra space, and since it is
allocated with malloc the function is AS-signal-unsafe. It should be
feasible to change it to use mmap, although I am not sure how urgent
it is. The heapsort is also nonstable, so programs that require a
stable sort would still be subject to this latent issue.
The tst-qsort5 is removed since it will not create quicksort adversarial
inputs with the current qsort_r implementation.
Checked on x86_64-linux-gnu and aarch64-linux-gnu.
Reviewed-by: Florian Weimer <fweimer@redhat.com>
The previous implementation did not consistently apply the rule that
the child nodes of node K are at 2 * K + 1 and 2 * K + 2, or
that the parent node is at (K - 1) / 2.
Add an internal test that targets the heapsort implementation
directly.
Reported-by: Stepan Golosunov <stepan@golosunov.pp.ru>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
