Fix grailsort block merging

Previously, we did not correctly handle some cases where a block contained
elements with a uniform value.

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: