Optimize buffer stealing step

We can implement this with just a merge step, rather than completely
resorting the b subsequence.

1 files changed, 16 insertions, 18 deletions

diff --git a/grailsort.c b/grailsort.c
index 3e86042..ca9d145 100644
--- a/grailsort.c
+++ b/grailsort.c
@@ -25,19 +25,8 @@ static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t widt
 	return bcount;
 }
 
-size_t merge(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t width, cmpfun cmp)
+void merge_preswapped(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t width, cmpfun cmp)
 {
-	struct counts snapshot = counts[CURRENT];
-
-	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;
 
@@ -55,6 +44,18 @@ size_t merge(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t wid
 	}
 
 	swap(buf, a, anmel * width);
+}
+
+size_t merge(char *buf, char *a, char *b, size_t anmel, size_t bnmel, size_t width, cmpfun cmp)
+{
+	struct counts snapshot = counts[CURRENT];
+
+	size_t skipa;
+	for (skipa = 0; cmp(a, b) <= 0; skipa++) a += width;
+	anmel -= skipa;
+
+	swap(buf, a, anmel * width);
+	merge_preswapped(a, buf, b, anmel, bnmel, width, cmp);
 
 	add_counts(counts + MERGE, &snapshot);
 	return skipa;
@@ -107,14 +108,11 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
 		} else {
 			stealb++;
 		}
-	} while (usebuf + stealb < bufnmel);
+	} while (stealb < bcount*blknmel && usebuf + stealb < bufnmel);
 	if (stealb) {
-		swap(a - stealb*width, b, stealb*width);
-		add_counts(counts + STEAL_BUF, &snapshot);
-		grailsort(b, bcount * blknmel, width, cmp);
-	} else {
-		add_counts(counts + STEAL_BUF, &snapshot);
+		merge_preswapped(b, a - stealb*width, b + stealb*width, stealb, bcount*blknmel - stealb, width, cmp);
 	}
+	add_counts(counts + STEAL_BUF, &snapshot);
 
 	/* sort all the a and b blocks together by their head elements */
 	grailsort(a, blocks, bwidth, cmp);