Skip to content

stdlib: implement qsort() as an introsort

Jeremy Soller requested to merge Arcterus:qsort-real into master

Created by: Arcterus

I've implemented qsort() as an introsort that switches to insertion sort on arrays smaller than 8 elements and where the pivot for partitioning is found using the median-of-three approach.

This builds on #122 (as that bug was found while testing this qsort()), but I can separate them if needed. I'll see if I can add usable tests later.

This isn't really relevant, but another consequence of my testing was that I discovered our printf() was very slow. Like the program I am using to test takes at least twice as long when using relibc instead of glibc because of the calls to printf() in the comparison function.

Merge request reports