From 111c49dac18a92523c0516da006049ab8a63df3d Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Sun, 29 Jun 2014 12:45:30 -0500 Subject: Don't roll a b block if it doesn't make sense to This added a pathological case where each iteration we'd roll a b block into place, just to have to do a giant rotate to move all the accumulated b blocks over to make room for the a block that should have been inserted next. --- wikisort.c | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-) diff --git a/wikisort.c b/wikisort.c index 2efa3ad..b2de063 100644 --- a/wikisort.c +++ b/wikisort.c @@ -96,18 +96,14 @@ static size_t roll(struct blockarray *a, struct blockarray *b, size_t bwidth, size_t width, char **mina, cmpfun cmp) { size_t iters = 0; - char *prevb; - - do { + while (b->blocks && cmp(b->base , *mina + bwidth - width) < 0) { swap(a->base, b->base, bwidth); if (*mina == a->base) *mina = b->base; - prevb = a->base; a->base += bwidth; b->base += bwidth; b->blocks--; iters++; - } while (b->blocks && cmp(prevb + bwidth - width, *mina) < 0); - + } return iters; } -- cgit v1.2.3