1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
43 #define THRESHOLD 16	/* Best choice for natural merge cut-off. */
77 	while (i -= ISIZE)
86 	while (i -= 1)
113 	int sense;  in mergesort_b()  local
120 		return (-1);  in mergesort_b()
131 		return (-1);  in mergesort_b()
143 	    	f2 = l1 = list1 + (p2 - list2);  in mergesort_b()
146 	    	l2 = list1 + (p2 - list2);  in mergesort_b()
151 	    			sense = -1;  in mergesort_b()
155 	    			sense = 0;  in mergesort_b()
158 				while ((b += size) < t && CMP(q, b) >sense)  in mergesort_b()
166 	    					if ((p = t - size) > b &&  in mergesort_b()
167 						    CMP(q, p) <= sense)  in mergesort_b()
172 	    				} else if (CMP(q, p) <= sense) {  in mergesort_b()
180 	    				i = (((t - b) / size) >> 1) * size;  in mergesort_b()
181 	    				if (CMP(q, p = b + i) <= sense)  in mergesort_b()
189 	    					p = b + (i >>= 1)) <= sense)  in mergesort_b()
245 		} while (--i);				\
246 		a -= size;				\
254 		} while (--i);				\
255 		s -= size2;				\
262  * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
268 	int i, length, size2, tmp, sense;  in setup()  local
282 	insertionsort(list1 + (n - i) * size, i, size, cmp);  in setup()
283 	last = list1 + size * (n - i);  in setup()
284 	*EVAL(list2 + (last - list1)) = list2 + n * size;  in setup()
289 	sense = (CMP(f1, f1 + size) > 0);  in setup()
290 	for (; f1 < last; sense = !sense) {  in setup()
292 					/* Find pairs with same sense. */  in setup()
294 			if ((CMP(f2, f2+ size) > 0) != sense)  in setup()
300 				p2 = *EVAL(p2) = f1 + size2 - list1 + list2;  in setup()
301 				if (sense > 0)  in setup()
307 				if ((CMP(f2-size, f2) > 0) != sense) {  in setup()
308 					p2 = *EVAL(p2) = f2 - list1 + list2;  in setup()
309 					if (sense > 0)  in setup()
310 						reverse(f1, f2-size);  in setup()
314 			if (sense > 0)  in setup()
315 				reverse (f1, f2-size);  in setup()
317 			if (f2 < last || CMP(f2 - size, f2) > 0)  in setup()
318 				p2 = *EVAL(p2) = f2 - list1 + list2;  in setup()
333  * This is to avoid out-of-bounds addresses in sorting the
342 	for (ai = a+size; --n >= 1; ai += size)  in insertionsort()
343 		for (t = ai; t > a; t -= size) {  in insertionsort()
344 			u = t - size;  in insertionsort()