diff options
| -rw-r--r-- | grailsort.c | 34 |
1 files changed, 16 insertions, 18 deletions
diff --git a/grailsort.c b/grailsort.c index 3e86042..ca9d145 100644 --- a/grailsort.c +++ b/grailsort.c @@ -25,19 +25,8 @@ static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t widt return bcount; } -size_t merge(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) +void merge_preswapped(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) { - struct counts snapshot = counts[CURRENT]; - - size_t skipa; - for (skipa = 0; cmp(a, b) <= 0; skipa++) a += width; - anmel -= skipa; - - swap(buf, a, anmel * width); - char *tmp = buf; - buf = a; - a = tmp; - while (anmel && bnmel) { size_t count; @@ -55,6 +44,18 @@ size_t merge(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t wid } swap(buf, a, anmel * width); +} + +size_t merge(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) +{ + struct counts snapshot = counts[CURRENT]; + + size_t skipa; + for (skipa = 0; cmp(a, b) <= 0; skipa++) a += width; + anmel -= skipa; + + swap(buf, a, anmel * width); + merge_preswapped(a, buf, b, anmel, bnmel, width, cmp); add_counts(counts + MERGE, &snapshot); return skipa; @@ -107,14 +108,11 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) } else { stealb++; } - } while (usebuf + stealb < bufnmel); + } while (stealb < bcount*blknmel && usebuf + stealb < bufnmel); if (stealb) { - swap(a - stealb*width, b, stealb*width); - add_counts(counts + STEAL_BUF, &snapshot); - grailsort(b, bcount * blknmel, width, cmp); - } else { - add_counts(counts + STEAL_BUF, &snapshot); + merge_preswapped(b, a - stealb*width, b + stealb*width, stealb, bcount*blknmel - stealb, width, cmp); } + add_counts(counts + STEAL_BUF, &snapshot); /* sort all the a and b blocks together by their head elements */ grailsort(a, blocks, bwidth, cmp); |