Add musl's old heap sort

3 files changed, 40 insertions, 2 deletions

diff --git a/musl_heapsort.c b/musl_heapsort.c
new file mode 100644
index 0000000..33a72d5
--- /dev/null
+++ b/musl_heapsort.c
@@ -0,0 +1,37 @@
+#include <stdlib.h>
+
+#include "sorters.h"
+#include "common.h"
+
+/* A simple heap sort implementation.. only in-place O(nlogn) sort I know. */
+
+#define MIN(a, b) ((a)<(b) ? (a) : (b))
+
+static void sift(char *base, size_t root, size_t nel, size_t width, int (*cmp)(const void *, const void *))
+{
+	size_t max;
+
+	while (2*root <= nel) {
+		max = 2*root;
+		if (max < nel && cmp(base+max*width, base+(max+1)*width) < 0)
+			max++;
+		if (max && cmp(base+root*width, base+max*width) < 0) {
+			swap(base+root*width, base+max*width, width);
+			root = max;
+		} else break;
+	}
+}
+
+void musl_heapsort(void *_base, size_t nel, size_t width, cmpfun cmp)
+{
+	char *base = _base;
+	size_t i;
+
+	if (!nel) return;
+	for (i=(nel+1)/2; i; i--)
+		sift(base, i-1, nel-1, width, cmp);
+	for (i=nel-1; i; i--) {
+		swap(base, base+i*width, width);
+		sift(base, 0, i-1, width, cmp);
+	}
+}
diff --git a/musl_qsort.c b/musl_smoothsort.c
index 3792aa1..4a1dfb1 100644
--- a/musl_qsort.c
+++ b/musl_smoothsort.c
@@ -154,7 +154,7 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2],
 	}
 }
 
-void musl_qsort(void *base, size_t nel, size_t width, cmpfun cmp)
+void musl_smoothsort(void *base, size_t nel, size_t width, cmpfun cmp)
 {
 	size_t lp[12*sizeof(size_t)];
 	size_t i, size = width * nel;
diff --git a/sorters.c b/sorters.c
index 43a3369..593ab29 100644
--- a/sorters.c
+++ b/sorters.c
@@ -7,7 +7,8 @@ const struct sorter sorters[] = {
 	{ .name = "freebsd",         .func = freebsd_qsort   },
 	{ .name = "glibc quicksort", .func = glibc_quicksort },
 	{ .name = "glibc mergesort", .func = glibc_mergesort },
-	{ .name = "musl",            .func = musl_qsort      },
+	{ .name = "musl smoothsort", .func = musl_smoothsort },
+	{ .name = "musl heapsort",   .func = musl_heapsort   },
 	{ .name = "wikisort",        .func = wikisort        },
 	{ .name = "wikisort (ref)",  .func = wikisort_ref    },
 	{ .name = "grailsort",       .func = grailsort       },