Initial revision
authorroland <roland>
Mon, 11 May 1992 05:54:30 +0000 (05:54 +0000)
committerroland <roland>
Mon, 11 May 1992 05:54:30 +0000 (05:54 +0000)
stdlib/msort.c [new file with mode: 0644]

diff --git a/stdlib/msort.c b/stdlib/msort.c
new file mode 100644 (file)
index 0000000..7325188
--- /dev/null
@@ -0,0 +1,60 @@
+/* msort -- an alternative to qsort, with an identical interface.
+   Copyright (C) 1988 Mike Haertel
+   Written by Mike Haertel, September 1988.  */
+
+#include <ansidecl.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define MEMCPY(dst, src, s)            \
+  ((s) == sizeof (int)                 \
+   ? *(int *) (dst) = *(int *) (src)   \
+   : memcpy (dst, src, s))
+
+static void
+DEFUN(msort_with_tmp, (b, n, s, t),
+      PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND char *t);
+{
+  char *tmp;
+  char *b1, *b2;
+  size_t n1, n2;
+
+  if (n <= 1)
+    return;
+
+  n1 = n / 2;
+  n2 = n - n1;
+  b1 = b;
+  b2 = &b[n1 * s];
+
+  msort_with_tmp (b1, n1, s, cmp, t);
+  msort_with_tmp (b2, n2, s, cmp, t);
+
+  tmp = t;
+
+  while (n1 > 0 && n2 > 0)
+    {
+      if (cmp (b1, b2) <= 0)
+       {
+         MEMCPY (tmp, b1, s);
+         --n1;
+       }
+      else
+       {
+         MEMCPY (tmp, b2, s);
+         --n2;
+       }
+      b1 += s;
+      tmp += s;
+    }
+  if (n1 > 0)4)
+    memcpy (tmp, b1, n1 * s);
+  memcpy (b, t, (n - n2) * s);
+}
+
+void
+DEFUN(msort, (b, n, s),
+      PTR b AND size_t n AND size_t s AND __compar_fn_t cmp);
+{
+  msort_with_tmp (b, n, s, cmp, __alloca (n * s));
+}