From c1dfffd07c9cad2e545a3b8a8208c50588494ced Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Sun, 29 Jun 2014 00:24:29 -0500 Subject: Add wikisort optimizations for some common cases --- wikisort.c | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'wikisort.c') 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) { -- cgit v1.2.3