add qsort as libc extension

[JonBruchim]

qsort isn't implemented under stdlib

As we would like zephyr to have a small memory footprint,
adding this function to stdlib (as its in the standard c library) will increase the overhead
I would like to add this function under zephyr/lib/libc/minimal/

I would be glad to take this as my first issue in zephyr.

Thanks

[andrewboie]

we use gc-sections so I don't see any particular issue with adding to minimal libc since if it is unused, its code won't be included in the binary.

[JonBruchim]

Ive actually made a PR adding musl libc implementation
but I've closed it after thinking again about the implementations made in subsys/shell/shell_module/src/qsort.c
should we remove them?
Ill open the PR again

[cfriedt]

Also covered in #31107

[cfriedt]

Copied from #29804

I have some reservations about just copying from another project, although I haven't looked at the implementation.

• qsort does not actually specify which sorting algorithm should be used under the hood, which leaves a lot of possibilities open for the implementation. I've read that musl has implemented Smoothsort
• if we add a sorting algorithm to the minimal libc, let's add one that has decent worst-case performance.
• if we add a sorting algorithm to the minimal libc, let's add one that has all of the other random features that we could want, such as
  • in place sorting (no external memory required)
  • stability (i.e. the input order of elements is preserved in the output)
  • A decent reference for some of these features are here:
    https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
    https://en.wikipedia.org/wiki/Qsort

I mistakenly opened #31107 for this same topic since I've been carrying qsort.c in my greybus module for a while (from the BSD C library). However, due to the aforementioned concerns, I never bothered to make a PR.

@JonBruchim - would you be able to provide some analysis of this vs possibly other algorithms?

Just at a quick glance, Block Sort looks promising too.

https://en.wikipedia.org/wiki/Block_sort

• O(N) best case
• O(NlogN) worst / average case
• O(1) space
• Stable
• In-place
  I haven't looked to see if it can be implemented easily though, or what kind of stack space it might require. That's also obviously a concern.

I guess the only slight advantage that Block Sort might have is that it's stable. Smoothsort looks to have a reasonably simple implementation though.

[cfriedt]

Discussed today in the release meeting, this change in #39980 may be backported to 2.7 because it:

• serves a purpose within Zephyr (testing the shell subsystem)
• improves API consistency without making any API changes
• same code can be built with both Newlib and the Minimal LibC
• fixes the logical inconsistency, namely
  • we can search through a sorted array (with bsearch())
  • we can not build a sorted array (with qsort())
• has had several requests:
  • undefined reference to `bsearch' #stdlib #15159
  • add qsort as libc extension  #28896
  • libc: minimal: add qsort routine #31107
  • subsys: greybus: remove qsort implementation cfriedt/greybus-for-zephyr#63 - (a separate patch is made on top of Zephyr for this purpose)

It satisfies several requirements of the Minimal LibC

• minimal amount of maintenance required
• small code footprint
• decent performance

Lastly, it satisfies several criteria for Safety Critical

• reasonable asymptotic bounds:
  • time: O(log(n)) in best, average, and worst cases
  • space: O(1)
• iterative solution as opposed to recursive
• operates in-place