Fill buffer with smallest elements

This avoids the need to distribute the buffer through the whole array at
the end.  It also allows us to skips most of the work for sorted and
reverse-sorted inputs.

3 files changed, 36 insertions, 3 deletions

diff --git a/counts.c b/counts.c
index d1f3910..f644706 100644
--- a/counts.c
+++ b/counts.c
@@ -30,7 +30,7 @@ void add_counts(struct counts *target, struct counts *snapshot)
 
 void print_counts(void)
 {
-	char *labels[] = {"total", "sortnet", "overlap", "merge", "move buffer", "distribute"};
+	char *labels[] = {"total", "sortnet", "check sorted", "steal buffer", "overlap", "merge", "distribute" };
 	for (int i = 0; i < MAX_COUNTS; i++) {
 		const struct counts *c = counts+i;
 		dprintf(42, "%12s: %10lu cmp, %10lu swap, %10lu rotate\n", labels[i], c->compare, c->swap, c->rotate);
diff --git a/counts.h b/counts.h
index 46e2e18..b066647 100644
--- a/counts.h
+++ b/counts.h
@@ -4,9 +4,10 @@
 enum {
 	CURRENT,
 	SORTNET,
+	CHECK_SORTED,
+	STEAL_BUF,
 	LAST_OVERLAP,
 	MERGE,
-	MOVE_BUFFER,
 	DISTRIBUTE,
 	MAX_COUNTS
 };
diff --git a/grailsort.c b/grailsort.c
index 9caf28f..2e0131a 100644
--- a/grailsort.c
+++ b/grailsort.c
@@ -83,6 +83,39 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
 	grailsort(buf, acount * blknmel + bufnmel, width, cmp);
 	grailsort(b,   bcount * blknmel,           width, cmp);
 
+	struct counts snapshot = counts[CURRENT];
+	int tmp = cmp(tail(a, acount*blknmel, width), b) <= 0;
+	add_counts(counts + CHECK_SORTED, &snapshot);
+	if (tmp) return;
+
+	snapshot = counts[CURRENT];
+	tmp = cmp(base, tail(b, bcount*blknmel, width)) >= 0;
+	if (tmp) {
+		rotate(base, nmel*width, acount*bwidth + bufnmel*width);
+		add_counts(counts + CHECK_SORTED, &snapshot);
+		return;
+	}
+	add_counts(counts + CHECK_SORTED, &snapshot);
+
+	/* steal some small elements from b for the buffer,
+	 * so the buffer has the bufnmel smallest elements */
+	size_t usebuf = 0, stealb = 0;
+	snapshot = counts[CURRENT];
+	do {
+		if (cmp(buf + usebuf*width, b + stealb*width) <= 0) {
+			usebuf++;
+		} else {
+			stealb++;
+		}
+	} while (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);
+	}
+
 	/* sort all the a and b blocks together by their head elements */
 	grailsort(a, blocks, bwidth, cmp);
 
@@ -102,7 +135,6 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
 	}
 
 	grailsort(buf, bufnmel, width, cmp);
-	distribute_buffer(buf, bufnmel, nmel - bufnmel, width, cmp);
 
 #if 0
 	assert_sorted(base, nmel, width, cmp);