From 97427b08ef4e91e31f7694fd691774c012f23dff Mon Sep 17 00:00:00 2001
From: Bobby Bingham <koorogi@koorogi.info>
Date: Sun, 2 Nov 2014 19:14:41 -0600
Subject: Switch to a stationary buffer, rather than moving it through the
 array

---
 grailsort.c | 72 ++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 35 insertions(+), 37 deletions(-)

diff --git a/grailsort.c b/grailsort.c
index 331452d..9caf28f 100644
--- a/grailsort.c
+++ b/grailsort.c
@@ -29,32 +29,35 @@ 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) {
-		for (count = 0; cmp(a_end-width, b_end-width) > 0; count++) {
-			anmel   -= 1;
-			bufnmel -= 1;
-			a_end   -= width;
-			buf_end -= width;
-		}
-		swap(a_end, buf_end, count*width);
+	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;
 
 		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);
+			for (count = 0; bnmel && count < anmel && cmp(a, b + count*width) > 0; count++) bnmel--;
+			swap(buf, b, count * width);
+			b   += count * width;
+			buf += count * width;
+		} while (count == anmel);
+
+		for (count = 0; anmel && cmp(a + count*width, b) <= 0; count++) anmel--;
+		swap(buf, a, count * width);
+		a   += count * width;
+		buf += count * width;
 	}
 
+	swap(buf, a, anmel * width);
+
 	add_counts(counts + MERGE, &snapshot);
-	return anmel;
+	return skipa;
 }
 
 void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
@@ -73,38 +76,33 @@ 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;
-	char *b   = a + acount * bwidth;
-	char *buf = b + bcount * bwidth;
+	char *buf = base;
+	char *a   = buf + bufnmel * width;
+	char *b   = a   + acount * bwidth;
 
-	grailsort(a, acount * blknmel, width, cmp);
-	grailsort(b, bcount * blknmel, width, cmp);
+	grailsort(buf, acount * blknmel + bufnmel, width, cmp);
+	grailsort(b,   bcount * blknmel,           width, cmp);
 
 	/* sort all the a and b blocks together by their head elements */
-	grailsort(base, blocks, bwidth, cmp);
+	grailsort(a, blocks, bwidth, cmp);
 
 	/* merge, starting from the end and working towards the beginning */
 	size_t last_nmel = blknmel;
 	while (blocks > 1) {
-		size_t overlap = last_overlap(base, blocks, bwidth, width, cmp);
+		size_t overlap = last_overlap(a, blocks, bwidth, width, cmp);
 
 		if (!overlap) break;
 
-		char *block_a = base + bwidth * (overlap-1);
-		char *block_b = base + bwidth *  overlap;
+		char *block_a = a + bwidth * (overlap-1);
+		char *block_b = block_a + bwidth;
 		size_t bnmel  = (blocks - overlap - 1) * blknmel + last_nmel;
 
 		last_nmel = merge(buf, block_a, block_b, bufnmel, blknmel, bnmel, width, cmp);
-		buf       = block_a + last_nmel * width;
 		blocks    = overlap;
 	}
 
-	struct counts snapshot = counts[CURRENT];
-	rotate(base, buf-base + bufnmel*width, buf-base);
-	add_counts(counts + MOVE_BUFFER, &snapshot);
-
-	grailsort(base, bufnmel, width, cmp);
-	distribute_buffer(base, bufnmel, nmel - bufnmel, width, cmp);
+	grailsort(buf, bufnmel, width, cmp);
+	distribute_buffer(buf, bufnmel, nmel - bufnmel, width, cmp);
 
 #if 0
 	assert_sorted(base, nmel, width, cmp);
-- 
cgit v1.2.3