diff options
Diffstat (limited to 'wikisort.c')
| -rw-r--r-- | wikisort.c | 25 |
1 files changed, 13 insertions, 12 deletions
@@ -168,22 +168,23 @@ void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) size_t bcount = nmel / bnmel; size_t bwidth = bnmel * width; - /* temporary buffer is at base. carve remainder of input into a and b subarrays. - * the nmels for these subarrays is specified in terms of blocks. */ - size_t bufnmel = bnmel + nmel % bnmel; - struct array a = { .base = base + width * bufnmel, .nmel = (bcount - 1) / 2 }; - struct array b = { .base = a.base + bwidth * a.nmel, .nmel = bcount - 1 - a.nmel }; + /* temporary buffer: nmel is measured in array elements */ + struct array buf = { .base = base, .nmel = bnmel + nmel % bnmel }; + + /* A and B subarrays: nmel is measured in blocks of bnmel elements each */ + struct array a = { .base = buf.base + width * buf.nmel, .nmel = (bcount - 1) / 2 }; + struct array b = { .base = a.base + bwidth * a.nmel, .nmel = bcount - 1 - a.nmel }; /* sort the buffer as if it were part of the a array */ - wikisort( base, nmel - b.nmel * bnmel, width, cmp); - wikisort(b.base, b.nmel * bnmel, width, cmp); + wikisort(buf.base, buf.nmel + a.nmel * bnmel, width, cmp); + wikisort(b.base, b.nmel * bnmel, width, cmp); /* if already sorted, nothing to do */ if (cmp(b.base - width, b.base) <= 0) return; /* if blocks in b are all less than those in a, just need a rotate */ if (cmp(base + (nmel - 1) * width, base) <= 0) { - rotate(base, nmel, width, a.nmel * bnmel + bufnmel); + rotate(base, nmel, width, a.nmel * bnmel + buf.nmel); return; } @@ -205,7 +206,7 @@ void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) /* merge any previous pending as and bs */ nmel_pend_b -= offset; if (nmel_pend_a && nmel_pend_b) { - merge_blocks(base, penda, nmel_pend_a, nmel_pend_b, width, cmp); + merge_blocks(buf.base, penda, nmel_pend_a, nmel_pend_b, width, cmp); } nmel_pend_a = bnmel; @@ -224,9 +225,9 @@ void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) } if (nmel_pend_a) { - merge_blocks(base, penda, nmel_pend_a, b.nmel * bnmel + nmel_pend_b, width, cmp); + merge_blocks(buf.base, penda, nmel_pend_a, b.nmel * bnmel + nmel_pend_b, width, cmp); } - wikisort(base, bufnmel, width, cmp); - distribute_buffer(base, bufnmel, nmel - bufnmel, width, cmp); + wikisort(buf.base, buf.nmel, width, cmp); + distribute_buffer(buf.base, buf.nmel, nmel - buf.nmel, width, cmp); } |