RADIXSORT(3)

💅 RADIXSORT(3) — the radix sort situation

okay so bestie, buckle up, we're talking about radixsort and sradixsort from the Library Functions Manual, section 3, living in the Standard C Library (libc, link it with -lc). this is literally the radix sort page and it's a whole vibe 💖

---

✨ SYNOPSIS ✨

like, here's the whole ritual, copy it exactly or it will not slay:

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

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, no cap.

what they do: they sort an array of pointers to byte strings, and the very first member of that array is the thing referenced by base. the byte strings can literally contain any values you want 🫶 — the end of each string is marked by the value you specify, called endbyte.

🌸 the table argument (the fun part)

you can absolutely specify your own sort order by passing the table argument. here's the tea:

• if table is non-NULL, it must reference an array of UCHAR_MAX + 1 bytes, and that array contains the sort weight of every possible byte value.
• the end-of-string byte must have a sort weight of 0 or 255 (that 255 is for sorting in reverse order, yes ma'am).
• more than one byte may have the same sort weight — that's not a bug, that's a feature.
• table is lowkey perfect for apps that want to sort different characters equally. for example: give A-Z the same weights as a-z and boom, you got yourself a case-insensitive sort ✨
• if table is NULL, the array gets sorted in ascending order according to the ASCII order of the byte strings they reference, and endbyte gets a sorting weight of 0.

🎀 stability check

• sradixsort() is stable — meaning if two elements compare as equal, their order in the sorted array is unchanged. she does not shuffle your equals. but she does use additional memory, exactly enough to hold nmemb pointers.
• radixsort() is not stable, but uses no additional memory. trade-offs, bestie 💀

👑 the algorithm lore

these functions 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 way they take linear time relative to the number of bytes in the strings?? obsessed. ⭐

---

🔥 RETURN VALUES 🔥

radixsort() returns the value 0 if successful. otherwise it returns the value -1 and the global variable errno is set to indicate the error. that's it, that's the whole deal.

---

😭 ERRORS 😭

• [EINVAL] — the value of the endbyte element of table is not 0 or 255. (you had ONE job 😤)

plus, sradixsort() may also fail and set errno for any of the errors specified for the library routine malloc(3). so like, memory things. keep an eye on 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. she's been serving since the old days 💜

---

and that's the page, bestie — this one shipped on Debian, dated January 27, 1994. ancient icon behavior fr fr, go sort something 🍓💅