1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
36  * Hybrid exponential search/linear search merge sort with hybrid
43 #define THRESHOLD 16	/* Best choice for natural merge cut-off. */
45 /* #define NATURAL to get hybrid natural merge.
77 	while (i -= ISIZE)
86 	while (i -= 1)
107 mergesort_b(void *base, size_t nmemb, size_t size, cmp_t cmp)  in mergesort_b()  argument
109 mergesort(void *base, size_t nmemb, size_t size, cmp_t cmp)  in mergesort_b()
120 		return (-1);  in mergesort_b()
127 	if (__is_aligned(size, ISIZE) && __is_aligned(base, ISIZE))  in mergesort_b()
131 		return (-1);  in mergesort_b()
133 	list1 = base;  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()
166 	    					if ((p = t - size) > b &&  in mergesort_b()
180 	    				i = (((t - b) / size) >> 1) * size;  in mergesort_b()
232 	if (base == list2) {  in mergesort_b()
245 		} while (--i);				\
246 		a -= size;				\
254 		} while (--i);				\
255 		s -= size2;				\
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()
298 		if (length < THRESHOLD) {		/* Pairwise merge */  in setup()
300 				p2 = *EVAL(p2) = f1 + size2 - list1 + list2;  in setup()
304 		} else {				/* Natural merge */  in setup()
307 				if ((CMP(f2-size, f2) > 0) != sense) {  in setup()
308 					p2 = *EVAL(p2) = f2 - list1 + list2;  in setup()
310 						reverse(f1, f2-size);  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()
323 #else		/* pairwise merge only. */  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()