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.

1 files 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);