From d95320cafb6d6b4a65f9713e54d83229cea1bbfa Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Wed, 29 Oct 2014 23:47:23 -0500 Subject: Perform swaps in larger chunks in merge step Provides about a 10% overall speedup for the sorted+noise and reverse+noise test cases. Increases the number of comparisons in some of the other cases, but doesn't significantly change the runtime. --- grailsort.c | 31 ++++++++++++++++++++----------- 1 file changed, 20 insertions(+), 11 deletions(-) diff --git a/grailsort.c b/grailsort.c index a39a0b2..331452d 100644 --- a/grailsort.c +++ b/grailsort.c @@ -29,19 +29,28 @@ size_t merge(char *buf, char *a, char *b, size_t bufnmel, size_t anmel, size_t b { struct counts snapshot = counts[CURRENT]; + char *a_end = a + width * anmel; + char *b_end = b + width * bnmel; + char *buf_end = buf + width * bufnmel; + size_t count; + while (bnmel) { - char *a_tail = tail(a, anmel, width); - char *b_tail = tail(b, bnmel, width); - char *buf_tail = tail(buf, bufnmel, width); - - if (cmp(a_tail, b_tail) <= 0) { - swap(buf_tail, b_tail, width); - bnmel--; - } else { - swap(buf_tail, a_tail, width); - anmel--; + for (count = 0; cmp(a_end-width, b_end-width) > 0; count++) { + anmel -= 1; + bufnmel -= 1; + a_end -= width; + buf_end -= width; } - bufnmel--; + swap(a_end, buf_end, count*width); + + do { + for (count = 0; bnmel && count < bufnmel && cmp(a_end-width, b_end-width) <= 0; count++) { + bnmel -= 1; + b_end -= width; + buf_end -= width; + } + swap(b_end, buf_end, count*width); + } while (count == bufnmel); } add_counts(counts + MERGE, &snapshot); -- cgit v1.2.3