1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
64 #define	THRESHOLD	20		/* Divert to simplesort(). */  macro
81 			return (-1);					\
106 	if (n < THRESHOLD)  in sradixsort()
110 			return (-1);  in sradixsort()
118 #define pop(a, n, i)	a = (--sp)->sa, n = sp->sn, i = sp->si
119 #define push(a, n, i)	sp->sa = a, sp->sn = n, (sp++)->si = i
122 /* Unstable, in-place sort. */
126 	static int count[256], nc, bmin;  in r_sort_a()  local
138 		if (n < THRESHOLD) {  in r_sort_a()
149 				if (++count[c] == 1 && c != endch) {  in r_sort_a()
166 		if (nc == 1 && count[bmin] == n) {  in r_sort_a()
168 			nc = count[bmin] = 0;  in r_sort_a()
174 		 * top[] = pointers to last out-of-place element in bins.  in r_sort_a()
175 		 * count[] = counts of elements in bins.  in r_sort_a()
176 		 * Before permuting: top[c-1] + count[c] = top[c];  in r_sort_a()
177 		 * during deal: top[c] counts down to top[c-1].  in r_sort_a()
182 			top[0] = ak = a + count[0];  in r_sort_a()
187 		for (cp = count + bmin; nc > 0; cp++) {  in r_sort_a()
188 			while (*cp == 0)	/* Find next non-empty pile. */  in r_sort_a()
197 			top[cp-count] = ak += *cp;  in r_sort_a()
198 			nc--;  in r_sort_a()
200 		swap(*sp0, *sp1, temp);	/* Play it safe -- biggest bin last. */  in r_sort_a()
211 		 *	aj<-aj + count[c] connects the bins in a linked list;  in r_sort_a()
212 		 *	reset count[c].  in r_sort_a()
214 		for (aj = a; aj < an;  *aj = r, aj += count[c], count[c] = 0)  in r_sort_a()
215 			for (r = *aj;  aj < (ak = --top[c = tr[r[i]]]);)  in r_sort_a()
225 	static int count[256], nc, bmin;  in r_sort_b()  local
236 		if (n < THRESHOLD) {  in r_sort_b()
243 			for (ak = a + n; --ak >= a;) {  in r_sort_b()
245 				if (++count[c] == 1 && c != endch) {  in r_sort_b()
260 			top[0] = ak = a + count[0];  in r_sort_b()
261 			count[0] = 0;  in r_sort_b()
265 			count[255] = 0;  in r_sort_b()
267 		for (cp = count + bmin; nc > 0; cp++) {  in r_sort_b()
277 			top[cp-count] = ak += c;  in r_sort_b()
278 			*cp = 0;			/* Reset count[]. */  in r_sort_b()
279 			nc--;  in r_sort_b()
284 			*--ak = *--ai;  in r_sort_b()
285 		for (ak = ta+n; --ak >= ta;)		/* Deal to piles. */  in r_sort_b()
286 			*--top[tr[(*ak)[i]]] = *ak;  in r_sort_b()
297 	for (ak = a+1; --n >= 1; ak++)  in simplesort()
298 		for (ai = ak; ai > a; ai--) {  in simplesort()
299 			for (s = ai[0] + b, t = ai[-1] + b;  in simplesort()
305 			swap(ai[0], ai[-1], s);  in simplesort()