Most of sorting an array in memory is wired up.

Signed-off-by: Gediminas Jakutis <gediminas@varciai.lt>

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);