replace `qsort()`

[MLopez-Ibanez]

qsort() in C is notoriously slow.

Either find a better implementation in pure C with an open-source license (MPL/MIT/Apache or similar) that allows inlining the comparator OR move to C++ and wrap the headers in extern "C".

[MLopez-Ibanez]

https://github.com/orlp/pdqsort/blob/master/pdqsort.h

https://github.com/swenson/sort/

[MLopez-Ibanez]

Or use timsort+powersort: https://github.com/python/cpython/blob/ea8ec95cfadbf58a11ef8e41341254d982a1a479/Objects/listobject.c#L2879

Or this version: https://github.com/sebawild/powersort

[tpgillam]

Other ideas, sticking to C:

• https://github.com/ahmadsalim/qsort-inline (Apple open source, APSL)
• https://github.com/attractivechaos/klib - specifically ksort.h, which is a really light-weight single header, no deps. several algs, introsort probably a good compromise. (MIT)
• https://github.com/contactandyc/the-macro-library - macro_sort. a bit heavier-weight than klib (multiple headers required), but same idea - (Apache 2.0)

[MLopez-Ibanez]

I'm all for incremental improvements. If somebody sumbits a PR that shows an improvement, that's better than the perfect solution.

[MLopez-Ibanez]

https://github.com/raygard/qsort_dev