diff options
Diffstat (limited to 'src/mergesort.c')
| -rw-r--r-- | src/mergesort.c | 30 |
1 files changed, 28 insertions, 2 deletions
diff --git a/src/mergesort.c b/src/mergesort.c index 2562d9d..c431b31 100644 --- a/src/mergesort.c +++ b/src/mergesort.c @@ -5,15 +5,41 @@ #include <errno.h> #include <stdlib.h> #include "defs.h" +#include "io.h" #include "mergesort.h" +/* bottom-up variantas */ + +int merge_sort(struct stream * const src, struct stream * const dest) +{ + int ret = 0; + struct stream tmp[4]; /* I can't into stream reuse, hence four. A yeet, followed by a dab. */ + size_t i; + + try(!src || !dest, err, EINVAL, "cannot sort what's not there"); + + if (src->n > 1) { /* stream of size one is inherently sorted */ + src->split(src, tmp, tmp + 2); /* split stream in half */ + merge_sort(tmp + 1, tmp); /* recurse-sort first half */ + merge_sort(tmp + 3, tmp + 2); /* recurse-sort second half */ + merge(dest, tmp, tmp + 2); /* merge the two halves back */ + } + + for (i = 0; i < (sizeof(tmp) / sizeof(*tmp)); ++i) { + stream_close(tmp + i); + } + +err: + return ret; +} + int merge(struct stream * const dest, struct stream * const A, struct stream * const B) { - int ret; + int ret = 0; struct entry_l *a; struct entry_l *b; - try(A->parent != B->parent, err, EINVAL, "cannot merge blocks: uncommon parent!"); + try(A->parentid != B->parentid, err, EINVAL, "cannot merge blocks: uncommon parent!"); a = get(A); b = get(B); |