diff options
| author | Adhemerval Zanella <adhemerval.zanella@linaro.org> | 2023-10-03 09:22:49 -0300 |
|---|---|---|
| committer | Adhemerval Zanella <adhemerval.zanella@linaro.org> | 2023-10-31 14:18:03 -0300 |
| commit | 274a46c9b25ab733a1fb9fb1497f1beecae30193 (patch) | |
| tree | 6bbc5910ee51e37f4dc0621b64554ae0a7e0db2d /stdlib/msort.c | |
| parent | d097f3c79be55d646d86efb7ce876bf84d5ebe4e (diff) | |
| download | glibc-274a46c9b25ab733a1fb9fb1497f1beecae30193.tar glibc-274a46c9b25ab733a1fb9fb1497f1beecae30193.tar.gz glibc-274a46c9b25ab733a1fb9fb1497f1beecae30193.tar.bz2 glibc-274a46c9b25ab733a1fb9fb1497f1beecae30193.zip | |
stdlib: Implement introsort for qsort (BZ 19305)
This patch makes the quicksort implementation to acts as introsort, to
avoid worse-case performance (and thus making it O(nlog n)). It switch
to heapsort when the depth level reaches 2*log2(total elements). The
heapsort is a textbook implementation.
Checked on x86_64-linux-gnu and aarch64-linux-gnu.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
Diffstat (limited to 'stdlib/msort.c')
0 files changed, 0 insertions, 0 deletions