radixsort(3bsd)

💖 radixsort — the radix sort bestie era 💖

okay so welcome to radixsort(3bsd), the BSD utility functions situation, living in libbsd and linking with -lbsd. this is the radixsort, sradixsort page and yes we're doing both of them, they're sisters, they're a duo, they ate. ✨

---

🌸 LIBRARY 🌸

Utility functions from BSD systems — that's libbsd, and you link it with -lbsd. 🫶

---

🎀 SYNOPSIS 🎀

#include <limits.h>
#include <stdlib.h>

(also pls check libbsd(7) for the whole include usage tea, bestie ☕)

int
radixsort(const unsigned char **base, int nmemb,
    const unsigned char *table, unsigned endbyte);

int
sradixsort(const unsigned char **base, int nmemb,
    const unsigned char *table, unsigned endbyte);

---

✨ DESCRIPTION ✨

So. radixsort() and sradixsort() are both implementations of radix sort. iconic behavior honestly. 👑

These functions sort an array of nmemb elements made of pointers to byte strings, and the very first member of that array is referenced by base. the byte strings can contain any values, like literally anything, they're not picky. the end of a string is marked by a character that has the same weight as the value you specify as endbyte. and heads up: endbyte has to be between 0 and 255. no in-between nonsense, that's the range, periodt. 💅

Now, if you wanna be fancy, apps can specify their own sort order by passing the table argument. if it's non-NULL, then table must reference an array of UCHAR_MAX + 1 bytes, and that array holds the sort weight of every possible byte value. 🌈

⚠️ the end-of-string byte must have a sort weight of 0 or 255 (and 255 is the one you use if you're sorting in reverse order). do not skip this. it's not a suggestion, bestie.

More than one byte can have the same sort weight, no drama there. and table is lowkey the whole reason you'd bother: it's for apps that want different characters to sort equally. for example, giving the same weights for A-Z as for a-z gets you a case-insensitive sort. chef's kiss. 😌

If table is NULL, then the contents of the array get sorted in ascending order according to the ASCII order of the byte strings they reference, and endbyte gets a sorting weight of 0.

Okay now the difference between the two functions, because this is the part everyone asks about:

• sradixsort() is stable — meaning if two elements compare as equal, their order in the sorted array stays exactly the same as it was. but it uses additional memory, enough to hold nmemb pointers. 💭
• radixsort() is not stable, but it uses no additional memory. tradeoffs, we love them. ⚖️

Both of these are variants of most-significant-byte radix sorting. specifically, go look at D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. and the slay part? they take linear time relative to the number of bytes in the strings. linear. we love a good time complexity. 🔥

---

🌟 RETURN VALUES 🌟

radixsort() returns the value 0 if everything went fine and dandy. otherwise it returns -1, and the global variable errno gets set to tell you what the error was. no cap. 💀

---

💜 ERRORS 💜

• [EINVAL] — the value of the endbyte element of table is not 0 or 255. like we said. it's 0 or 255. that's the rule. 🙈

and additionally, sradixsort() may also fail and set errno for any of the errors specified for the library routine malloc(3). memory said no, and honestly, valid of it. 😭

---

🦋 SEE ALSO 🦋

• sort(1), qsort(3)
• Knuth, D.E., "Sorting and Searching", The Art of Computer Programming, Vol. 3, pp. 170-178, 1968.
• Paige, R., "Three Partition Refinement Algorithms", SIAM J. Comput., No. 6, Vol. 16, 1987.
• McIlroy, P., "Computing Systems", Engineering Radix Sort, Vol. 6:1, pp. 5-27, 1993.

---

👑 HISTORY 👑

The radixsort() function first appeared in 4.4BSD. ancient. legendary. still here. 🧚

---

okay that's the whole page bestie, mwah 💋 — this one comes from the Debian crowd and it's dated January 27, 1994, which is literally older than most of us, and it lives in section 3bsd. go forth and sort. slay. 🌸✨💖