AxlSort — In-Place Sorting

axl_qsort is a drop-in for qsort(3) with a guaranteed O(n log n) worst case and no heap allocation. The engine is an introsort: median-of-three quicksort, insertion sort for small runs, and a heapsort fallback when recursion depth exceeds 2*log2(n). It is not stable. axl_array_sort delegates to it.

Header: <axl/axl-sort.h>

API Reference

Functions

void axl_qsort(void *base, size_t nmemb, size_t size, AxlCompareFunc compare)

Sort nmemb elements of size bytes in place (introsort).

axl-sort.h:

In-place sort over a raw element buffer — the qsort(3) shape, but with a fixed worst case. The engine is an introsort (median-of-three quicksort, insertion sort for small runs, heapsort fallback when the recursion depth exceeds 2*log2(n)). That guarantees O(n log n) worst case while doing no heap allocation and keeping stack depth bounded — the right trade for a freestanding/UEFI environment where malloc can fail and stacks are small.

The sort is NOT stable: equal elements may be reordered. Comparators use the shared AxlCompareFunc / AxlCompareDataFunc typedefs and follow the standard < 0 / 0 / > 0 convention.

Drop-in for qsort(3): same argument shape and comparator convention, but with a guaranteed O(n log n) worst case and no allocation. Not stable. No-op if base is NULL, compare is NULL, size is 0, or nmemb is less than 2.

Parameters:

  • base – start of the element buffer

  • nmemb – number of elements

  • size – size of each element in bytes

  • compare – comparison function (qsort-compatible)

void axl_qsort_with_data(void *base, size_t nmemb, size_t size, AxlCompareDataFunc compare, void *user_data)

Sort in place with a context-aware comparator (introsort).

Like axl_qsort() but threads user_data through every comparison — the qsort_r(3) shape. Not stable. Same no-op guards as axl_qsort().

Parameters:

  • base – start of the element buffer

  • nmemb – number of elements

  • size – size of each element in bytes

  • compare – comparison function with user_data

  • user_data – passed to every compare call