From ab27fe8c3edda02a2bd6088b07aa8c13a561a24d Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Thu, 31 Jul 2014 20:46:33 -0500 Subject: Don't pre-sort the temp swap buffer This is a close call. On the one hand, this buffer will get jumbled when used for merging adjacent blocks, so we'll need to sort it again before distributing it. On the other hand, by sorting it early, we know that we won't have to distribute it very far. In testing, pre-sorting seems to lose out overall. --- grailsort.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/grailsort.c b/grailsort.c index 6e360dc..67528ca 100644 --- a/grailsort.c +++ b/grailsort.c @@ -61,12 +61,12 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) char *a = base + bufnmel * width; char *b = a + acount * bwidth; - /* sort the buffer as if it were part of the a array */ - grailsort(base, bufnmel + acount * blknmel, width, cmp); - grailsort(b, bcount * blknmel, width, cmp); + grailsort(a, acount * blknmel, width, cmp); + grailsort(b, bcount * blknmel, width, cmp); /* if already sorted, nothing to do */ - if (cmp(TAIL(a, acount * blknmel, width), b) <= 0) return; + if (cmp(TAIL(a, acount * blknmel, width), b) <= 0) + goto distribute; /* sort all the a and b blocks together by their head elements */ grailsort(a, blocks, bwidth, cmp); @@ -80,6 +80,7 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) blocks = overlap; } +distribute: grailsort(base, bufnmel, width, cmp); distribute_buffer(base, bufnmel, nmel - bufnmel, width, cmp); } -- cgit v1.2.3