From 26ab990a747ab675bcff32a40734dcb61468f652 Mon Sep 17 00:00:00 2001 From: Gediminas Jakutis Date: Wed, 17 Feb 2021 08:57:56 +0200 Subject: Most of sorting an array in memory is wired up. Signed-off-by: Gediminas Jakutis --- src/mergesort.c | 30 ++++++++++++++++++++++++++++-- 1 file changed, 28 insertions(+), 2 deletions(-) (limited to 'src/mergesort.c') 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 #include #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); -- cgit v1.2.3