From 83da373b9cbf7687a6db1a8fa8144692e582a297 Mon Sep 17 00:00:00 2001
From: Tom London <tbl@research.uucp>
Date: Fri, 19 Jan 1979 23:50:18 -0500
Subject: [PATCH] Bell 32V development Work on file usr/src/libc/gen/qsort.c

Co-Authored-By: John Reiser <jfr@research.uucp>
Synthesized-from: 32v
---
 usr/src/libc/gen/qsort.c | 120 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 120 insertions(+)
 create mode 100755 usr/src/libc/gen/qsort.c

diff --git a/usr/src/libc/gen/qsort.c b/usr/src/libc/gen/qsort.c
new file mode 100755
index 0000000000..202c759222
--- /dev/null
+++ b/usr/src/libc/gen/qsort.c
@@ -0,0 +1,120 @@
+
+static int	(*qscmp)();
+static int	qses;
+
+qsort(a, n, es, fc)
+char *a;
+unsigned n;
+int es;
+int (*fc)();
+{
+	qscmp = fc;
+	qses = es;
+	qs1(a, a+n*es);
+}
+
+static qs1(a, l)
+char *a, *l;
+{
+	register char *i, *j;
+	register es;
+	char **k;
+	char *lp, *hp;
+	int c;
+	unsigned n;
+
+
+	es = qses;
+
+start:
+	if((n=l-a) <= es)
+		return;
+	n = es * (n / (2*es));
+	hp = lp = a+n;
+	i = a;
+	j = l-es;
+	for(;;) {
+		if(i < lp) {
+			if((c = (*qscmp)(i, lp)) == 0) {
+				qsexc(i, lp -= es);
+				continue;
+			}
+			if(c < 0) {
+				i += es;
+				continue;
+			}
+		}
+
+loop:
+		if(j > hp) {
+			if((c = (*qscmp)(hp, j)) == 0) {
+				qsexc(hp += es, j);
+				goto loop;
+			}
+			if(c > 0) {
+				if(i == lp) {
+					qstexc(i, hp += es, j);
+					i = lp += es;
+					goto loop;
+				}
+				qsexc(i, j);
+				j -= es;
+				i += es;
+				continue;
+			}
+			j -= es;
+			goto loop;
+		}
+
+
+		if(i == lp) {
+			if(lp-a >= l-hp) {
+				qs1(hp+es, l);
+				l = lp;
+			} else {
+				qs1(a, lp);
+				a = hp+es;
+			}
+			goto start;
+		}
+
+
+		qstexc(j, lp -= es, i);
+		j = hp -= es;
+	}
+}
+
+static qsexc(i, j)
+char *i, *j;
+{
+	register char *ri, *rj, c;
+	int n;
+
+	n = qses;
+	ri = i;
+	rj = j;
+	do {
+		c = *ri;
+		*ri++ = *rj;
+		*rj++ = c;
+	} while(--n);
+}
+
+static qstexc(i, j, k)
+char *i, *j, *k;
+{
+	register char *ri, *rj, *rk;
+	int c;
+	int n;
+
+	n = qses;
+	ri = i;
+	rj = j;
+	rk = k;
+	do {
+		c = *ri;
+		*ri++ = *rk;
+		*rk++ = *rj;
+		*rj++ = c;
+	} while(--n);
+}
-- 
2.20.1