2 * sssort.c for libdivsufsort
3 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
27 #include "divsufsort_private.h"
30 /*- Private Functions -*/
32 static const saint_t lg_table[256]= {
33 -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
34 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
35 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
36 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
37 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
38 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
39 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
40 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
43 #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
49 # if defined(BUILD_DIVSUFSORT64)
53 56 + lg_table[(n >> 56) & 0xff] :
54 48 + lg_table[(n >> 48) & 0xff]) :
56 40 + lg_table[(n >> 40) & 0xff] :
57 32 + lg_table[(n >> 32) & 0xff])) :
60 24 + lg_table[(n >> 24) & 0xff] :
61 16 + lg_table[(n >> 16) & 0xff]) :
63 8 + lg_table[(n >> 8) & 0xff] :
64 0 + lg_table[(n >> 0) & 0xff]));
66 return (n & 0xffff0000) ?
68 24 + lg_table[(n >> 24) & 0xff] :
69 16 + lg_table[(n >> 16) & 0xff]) :
71 8 + lg_table[(n >> 8) & 0xff] :
72 0 + lg_table[(n >> 0) & 0xff]);
74 #elif SS_BLOCKSIZE < 256
78 8 + lg_table[(n >> 8) & 0xff] :
79 0 + lg_table[(n >> 0) & 0xff];
83 #endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
87 static const saint_t sqq_table[256] = {
88 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61,
89 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84, 86, 87, 89,
90 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109,
91 110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126,
92 128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142,
93 143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155,
94 156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
95 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180,
96 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191,
97 192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201,
98 202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211,
99 212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221,
100 221, 222, 222, 223, 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230,
101 230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
102 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247,
103 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255
108 ss_isqrt(saidx_t x) {
111 if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; }
112 e = (x & 0xffff0000) ?
114 24 + lg_table[(x >> 24) & 0xff] :
115 16 + lg_table[(x >> 16) & 0xff]) :
117 8 + lg_table[(x >> 8) & 0xff] :
118 0 + lg_table[(x >> 0) & 0xff]);
121 y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7);
122 if(e >= 24) { y = (y + 1 + x / y) >> 1; }
123 y = (y + 1 + x / y) >> 1;
125 y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1;
127 return sqq_table[x] >> 4;
130 return (x < (y * y)) ? y - 1 : y;
133 #endif /* SS_BLOCKSIZE != 0 */
136 /*---------------------------------------------------------------------------*/
138 /* Compares two suffixes. */
141 ss_compare(const sauchar_t *T,
142 const saidx_t *p1, const saidx_t *p2,
144 const sauchar_t *U1, *U2, *U1n, *U2n;
146 for(U1 = T + depth + *p1,
147 U2 = T + depth + *p2,
148 U1n = T + *(p1 + 1) + 2,
149 U2n = T + *(p2 + 1) + 2;
150 (U1 < U1n) && (U2 < U2n) && (*U1 == *U2);
155 (U2 < U2n ? *U1 - *U2 : 1) :
160 /*---------------------------------------------------------------------------*/
162 #if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1)
164 /* Insertionsort for small size groups */
167 ss_insertionsort(const sauchar_t *T, const saidx_t *PA,
168 saidx_t *first, saidx_t *last, saidx_t depth) {
173 for(i = last - 2; first <= i; --i) {
174 for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) {
175 do { *(j - 1) = *j; } while((++j < last) && (*j < 0));
176 if(last <= j) { break; }
178 if(r == 0) { *j = ~*j; }
183 #endif /* (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) */
186 /*---------------------------------------------------------------------------*/
188 #if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
192 ss_fixdown(const sauchar_t *Td, const saidx_t *PA,
193 saidx_t *SA, saidx_t i, saidx_t size) {
198 for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
199 d = Td[PA[SA[k = j++]]];
200 if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; }
201 if(d <= c) { break; }
206 /* Simple top-down heapsort. */
209 ss_heapsort(const sauchar_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size) {
214 if((size % 2) == 0) {
216 if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); }
219 for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); }
220 if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); }
221 for(i = m - 1; 0 < i; --i) {
222 t = SA[0], SA[0] = SA[i];
223 ss_fixdown(Td, PA, SA, 0, i);
229 /*---------------------------------------------------------------------------*/
231 /* Returns the median of three elements. */
234 ss_median3(const sauchar_t *Td, const saidx_t *PA,
235 saidx_t *v1, saidx_t *v2, saidx_t *v3) {
237 if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); }
238 if(Td[PA[*v2]] > Td[PA[*v3]]) {
239 if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; }
245 /* Returns the median of five elements. */
248 ss_median5(const sauchar_t *Td, const saidx_t *PA,
249 saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5) {
251 if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); }
252 if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); }
253 if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); }
254 if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); }
255 if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); }
256 if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; }
260 /* Returns the pivot element. */
263 ss_pivot(const sauchar_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last) {
268 middle = first + t / 2;
272 return ss_median3(Td, PA, first, middle, last - 1);
275 return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1);
279 first = ss_median3(Td, PA, first, first + t, first + (t << 1));
280 middle = ss_median3(Td, PA, middle - t, middle, middle + t);
281 last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1);
282 return ss_median3(Td, PA, first, middle, last);
286 /*---------------------------------------------------------------------------*/
288 /* Binary partition for substrings. */
291 ss_partition(const saidx_t *PA,
292 saidx_t *first, saidx_t *last, saidx_t depth) {
295 for(a = first - 1, b = last;;) {
296 for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; }
297 for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { }
298 if(b <= a) { break; }
303 if(first < a) { *first = ~*first; }
307 /* Multikey introsort for medium size groups. */
310 ss_mintrosort(const sauchar_t *T, const saidx_t *PA,
311 saidx_t *first, saidx_t *last,
313 #define STACK_SIZE SS_MISORT_STACKSIZE
314 struct { saidx_t *a, *b, c; saint_t d; } stack[STACK_SIZE];
316 saidx_t *a, *b, *c, *d, *e, *f;
322 for(ssize = 0, limit = ss_ilg(last - first);;) {
324 if((last - first) <= SS_INSERTIONSORT_THRESHOLD) {
325 #if 1 < SS_INSERTIONSORT_THRESHOLD
326 if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); }
328 STACK_POP(first, last, depth, limit);
333 if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); }
335 for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) {
336 if((x = Td[PA[*a]]) != v) {
337 if(1 < (a - first)) { break; }
342 if(Td[PA[*first] - 1] < v) {
343 first = ss_partition(PA, first, a, depth);
345 if((a - first) <= (last - a)) {
346 if(1 < (a - first)) {
347 STACK_PUSH(a, last, depth, -1);
348 last = a, depth += 1, limit = ss_ilg(a - first);
350 first = a, limit = -1;
354 STACK_PUSH(first, a, depth + 1, ss_ilg(a - first));
355 first = a, limit = -1;
357 last = a, depth += 1, limit = ss_ilg(a - first);
364 a = ss_pivot(Td, PA, first, last);
369 for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { }
370 if(((a = b) < last) && (x < v)) {
371 for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) {
372 if(x == v) { SWAP(*b, *a); ++a; }
375 for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { }
376 if((b < (d = c)) && (x > v)) {
377 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
378 if(x == v) { SWAP(*c, *d); --d; }
383 for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) {
384 if(x == v) { SWAP(*b, *a); ++a; }
386 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
387 if(x == v) { SWAP(*c, *d); --d; }
394 if((s = a - first) > (t = b - a)) { s = t; }
395 for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
396 if((s = d - c) > (t = last - d - 1)) { s = t; }
397 for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
399 a = first + (b - a), c = last - (d - c);
400 b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth);
402 if((a - first) <= (last - c)) {
403 if((last - c) <= (c - b)) {
404 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
405 STACK_PUSH(c, last, depth, limit);
407 } else if((a - first) <= (c - b)) {
408 STACK_PUSH(c, last, depth, limit);
409 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
412 STACK_PUSH(c, last, depth, limit);
413 STACK_PUSH(first, a, depth, limit);
414 first = b, last = c, depth += 1, limit = ss_ilg(c - b);
417 if((a - first) <= (c - b)) {
418 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
419 STACK_PUSH(first, a, depth, limit);
421 } else if((last - c) <= (c - b)) {
422 STACK_PUSH(first, a, depth, limit);
423 STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
426 STACK_PUSH(first, a, depth, limit);
427 STACK_PUSH(c, last, depth, limit);
428 first = b, last = c, depth += 1, limit = ss_ilg(c - b);
433 if(Td[PA[*first] - 1] < v) {
434 first = ss_partition(PA, first, last, depth);
435 limit = ss_ilg(last - first);
443 #endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
446 /*---------------------------------------------------------------------------*/
448 #if SS_BLOCKSIZE != 0
452 ss_blockswap(saidx_t *a, saidx_t *b, saidx_t n) {
454 for(; 0 < n; --n, ++a, ++b) {
455 t = *a, *a = *b, *b = t;
461 ss_rotate(saidx_t *first, saidx_t *middle, saidx_t *last) {
464 l = middle - first, r = last - middle;
465 for(; (0 < l) && (0 < r);) {
466 if(l == r) { ss_blockswap(first, middle, l); break; }
468 a = last - 1, b = middle - 1;
471 *a-- = *b, *b-- = *a;
475 if((r -= l + 1) <= l) { break; }
476 a -= 1, b = middle - 1;
481 a = first, b = middle;
484 *a++ = *b, *b++ = *a;
488 if((l -= r + 1) <= r) { break; }
498 /*---------------------------------------------------------------------------*/
502 ss_inplacemerge(const sauchar_t *T, const saidx_t *PA,
503 saidx_t *first, saidx_t *middle, saidx_t *last,
512 if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); }
513 else { x = 0; p = PA + *(last - 1); }
514 for(a = first, len = middle - first, half = len >> 1, r = -1;
516 len = half, half >>= 1) {
518 q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth);
521 half -= (len & 1) ^ 1;
527 if(r == 0) { *a = ~*a; }
528 ss_rotate(a, middle, last);
531 if(first == middle) { break; }
534 if(x != 0) { while(*--last < 0) { } }
535 if(middle == last) { break; }
540 /*---------------------------------------------------------------------------*/
542 /* Merge-forward with internal buffer. */
545 ss_mergeforward(const sauchar_t *T, const saidx_t *PA,
546 saidx_t *first, saidx_t *middle, saidx_t *last,
547 saidx_t *buf, saidx_t depth) {
548 saidx_t *a, *b, *c, *bufend;
552 bufend = buf + (middle - first) - 1;
553 ss_blockswap(buf, first, middle - first);
555 for(t = *(a = first), b = buf, c = middle;;) {
556 r = ss_compare(T, PA + *b, PA + *c, depth);
560 if(bufend <= b) { *bufend = t; return; }
565 *a++ = *c, *c++ = *a;
567 while(b < bufend) { *a++ = *b, *b++ = *a; }
576 if(bufend <= b) { *bufend = t; return; }
581 *a++ = *c, *c++ = *a;
583 while(b < bufend) { *a++ = *b, *b++ = *a; }
592 /* Merge-backward with internal buffer. */
595 ss_mergebackward(const sauchar_t *T, const saidx_t *PA,
596 saidx_t *first, saidx_t *middle, saidx_t *last,
597 saidx_t *buf, saidx_t depth) {
598 const saidx_t *p1, *p2;
599 saidx_t *a, *b, *c, *bufend;
604 bufend = buf + (last - middle) - 1;
605 ss_blockswap(buf, middle, last - middle);
608 if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; }
609 else { p1 = PA + *bufend; }
610 if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; }
611 else { p2 = PA + *(middle - 1); }
612 for(t = *(a = last - 1), b = bufend, c = middle - 1;;) {
613 r = ss_compare(T, p1, p2, depth);
615 if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
617 if(b <= buf) { *buf = t; break; }
619 if(*b < 0) { p1 = PA + ~*b; x |= 1; }
620 else { p1 = PA + *b; }
622 if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
623 *a-- = *c, *c-- = *a;
625 while(buf < b) { *a-- = *b, *b-- = *a; }
629 if(*c < 0) { p2 = PA + ~*c; x |= 2; }
630 else { p2 = PA + *c; }
632 if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
634 if(b <= buf) { *buf = t; break; }
636 if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
637 *a-- = *c, *c-- = *a;
639 while(buf < b) { *a-- = *b, *b-- = *a; }
643 if(*b < 0) { p1 = PA + ~*b; x |= 1; }
644 else { p1 = PA + *b; }
645 if(*c < 0) { p2 = PA + ~*c; x |= 2; }
646 else { p2 = PA + *c; }
651 /* D&C based merge. */
654 ss_swapmerge(const sauchar_t *T, const saidx_t *PA,
655 saidx_t *first, saidx_t *middle, saidx_t *last,
656 saidx_t *buf, saidx_t bufsize, saidx_t depth) {
657 #define STACK_SIZE SS_SMERGE_STACKSIZE
658 #define GETIDX(a) ((0 <= (a)) ? (a) : (~(a)))
659 #define MERGE_CHECK(a, b, c)\
662 (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\
665 if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\
669 struct { saidx_t *a, *b, *c; saint_t d; } stack[STACK_SIZE];
670 saidx_t *l, *r, *lm, *rm;
671 saidx_t m, len, half;
675 for(check = 0, ssize = 0;;) {
676 if((last - middle) <= bufsize) {
677 if((first < middle) && (middle < last)) {
678 ss_mergebackward(T, PA, first, middle, last, buf, depth);
680 MERGE_CHECK(first, last, check);
681 STACK_POP(first, middle, last, check);
685 if((middle - first) <= bufsize) {
687 ss_mergeforward(T, PA, first, middle, last, buf, depth);
689 MERGE_CHECK(first, last, check);
690 STACK_POP(first, middle, last, check);
694 for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1;
696 len = half, half >>= 1) {
697 if(ss_compare(T, PA + GETIDX(*(middle + m + half)),
698 PA + GETIDX(*(middle - m - half - 1)), depth) < 0) {
700 half -= (len & 1) ^ 1;
705 lm = middle - m, rm = middle + m;
706 ss_blockswap(lm, middle, m);
707 l = r = middle, next = 0;
711 if(first < lm) { for(; *--l < 0;) { } next |= 4; }
713 } else if(first < lm) {
714 for(; *r < 0; ++r) { }
719 if((l - first) <= (last - r)) {
720 STACK_PUSH(r, rm, last, (next & 3) | (check & 4));
721 middle = lm, last = l, check = (check & 3) | (next & 4);
723 if((next & 2) && (r == middle)) { next ^= 6; }
724 STACK_PUSH(first, lm, l, (check & 3) | (next & 4));
725 first = r, middle = rm, check = (next & 3) | (check & 4);
728 if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) {
731 MERGE_CHECK(first, last, check);
732 STACK_POP(first, middle, last, check);
738 #endif /* SS_BLOCKSIZE != 0 */
741 /*---------------------------------------------------------------------------*/
747 sssort(const sauchar_t *T, const saidx_t *PA,
748 saidx_t *first, saidx_t *last,
749 saidx_t *buf, saidx_t bufsize,
750 saidx_t depth, saidx_t n, saint_t lastsuffix) {
752 #if SS_BLOCKSIZE != 0
753 saidx_t *b, *middle, *curbuf;
754 saidx_t j, k, curbufsize, limit;
758 if(lastsuffix != 0) { ++first; }
760 #if SS_BLOCKSIZE == 0
761 ss_mintrosort(T, PA, first, last, depth);
763 if((bufsize < SS_BLOCKSIZE) &&
764 (bufsize < (last - first)) &&
765 (bufsize < (limit = ss_isqrt(last - first)))) {
766 if(SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; }
767 buf = middle = last - limit, bufsize = limit;
769 middle = last, limit = 0;
771 for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) {
772 #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
773 ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth);
774 #elif 1 < SS_BLOCKSIZE
775 ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth);
777 curbufsize = last - (a + SS_BLOCKSIZE);
778 curbuf = a + SS_BLOCKSIZE;
779 if(curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; }
780 for(b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) {
781 ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth);
784 #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
785 ss_mintrosort(T, PA, a, middle, depth);
786 #elif 1 < SS_BLOCKSIZE
787 ss_insertionsort(T, PA, a, middle, depth);
789 for(k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
791 ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
796 #if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
797 ss_mintrosort(T, PA, middle, last, depth);
798 #elif 1 < SS_BLOCKSIZE
799 ss_insertionsort(T, PA, middle, last, depth);
801 ss_inplacemerge(T, PA, first, middle, last, depth);
805 if(lastsuffix != 0) {
806 /* Insert last type B* suffix. */
807 saidx_t PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2;
808 for(a = first, i = *(first - 1);
809 (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth)));