diff options
| -rw-r--r-- | grailsort.c | 56 |
1 files changed, 28 insertions, 28 deletions
diff --git a/grailsort.c b/grailsort.c index a585b2b..29bd694 100644 --- a/grailsort.c +++ b/grailsort.c @@ -15,24 +15,24 @@ static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t widt return bcount; } -void merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) +size_t merge(char *base, size_t anmel, size_t bnmel, size_t bufnmel, size_t width, cmpfun cmp) { - char *a = buf; - char *b = base + anmel * width; - - size_t skip = binary_search(b, base, anmel, width, cmp); - anmel -= skip; - base += skip * width; - - swap(base, a, anmel * width); - - while (anmel && bnmel) { - if (cmp(a, b) <= 0) { swap(base, a, width); a += width; anmel--; } - else { swap(base, b, width); b += width; bnmel--; } - base += width; + char *a_end = base + anmel * width; + char *b_end = a_end + bnmel * width; + char *buf_end = b_end + bufnmel * width; + size_t count = 0; + + while (bnmel) { + char *a = a_end - width; + char *b = b_end - width; + char *buf = buf_end - width; + + if (cmp(a, b) > 0) { swap(a, buf, width); a_end = a; anmel--; } + else { swap(b, buf, width); b_end = b; bnmel--; } + count++; + buf_end = buf; } - - swap(base, a, anmel * width); + return count; } void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) @@ -51,26 +51,26 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) size_t acount = blocks / 2; size_t bcount = blocks - acount; - char *a = base + bufnmel * width; - char *b = a + acount * bwidth; - + char *a = base; + char *b = a + acount * bwidth; grailsort(a, acount * blknmel, width, cmp); grailsort(b, bcount * blknmel, width, cmp); - /* if already sorted, nothing to do */ - if (cmp(TAIL(a, acount * blknmel, width), b) <= 0) - goto distribute; - /* sort all the a and b blocks together by their head elements */ - grailsort(a, blocks, bwidth, cmp); + grailsort(base, blocks, bwidth, cmp); /* merge, starting from the end and working towards the beginning */ + size_t bufidx = blocks * blknmel; while (blocks > 1) { - size_t overlap = last_overlap(a, blocks, bwidth, width, cmp); - if (overlap > 0) { - merge(base, TAIL(a, overlap, bwidth), blknmel, (blocks - overlap) * blknmel, width, cmp); + size_t overlap = last_overlap(base, blocks, bwidth, width, cmp); + if (overlap) { + bufidx -= merge(TAIL(base, overlap, bwidth), blknmel, bufidx - overlap*blknmel, bufnmel, width, cmp); } - blocks = overlap; + blocks = overlap; + } + + if (bufidx) { + rotate(base, (bufidx + bufnmel) * width, bufidx * width); } distribute: |