Add wikisort optimizations for some common cases

1 files changed, 9 insertions, 0 deletions

diff --git a/wikisort.c b/wikisort.c
index 8b27c57..2efa3ad 100644
--- a/wikisort.c
+++ b/wikisort.c
@@ -182,6 +182,15 @@ void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
 	wikisort(  base, nmel - b.blocks * bnmel, width, cmp);
 	wikisort(b.base,        b.blocks * bnmel, width, cmp);
 
+	/* if already sorted, nothing to do */
+	if (cmp(b.base - width, b.base) <= 0) return;
+
+	/* if blocks in b are all less than those in a, just need a rotate */
+	if (cmp(base + (nmel - 1) * width, base) <= 0) {
+		rotate(base, nmel, width, a.blocks * bnmel + bufnmel);
+		return;
+	}
+
 	size_t nmel_pend_a = 0, nmel_pend_b = 0;
 	char *mina = a.base, *penda;
 	while (a.blocks) {