1 files changed, 73 insertions, 0 deletions
diff --git a/sys/fmtio/strsrt.x b/sys/fmtio/strsrt.x
new file mode 100644
index 00000000..67318f01
--- /dev/null
+++ b/sys/fmtio/strsrt.x
@@ -0,0 +1,73 @@
+# Copyright(c) 1986 Association of Universities for Research in Astronomy Inc.
+
+define	LOGPTR	20		# log2(maxpts)  (1e6)
+
+# STRSRT -- Sort a list of strings, given an array of indices pointing into a
+# string buffer (e.g., sbuf=1 is Memc).  The sort is performed by permutation
+# of the index array.
+
+procedure strsrt (x, sb, nstr)
+
+int	x[ARB]			# array of string pointers or indices
+char	sb[ARB]			# string buffer
+int	nstr			# number of strings
+
+int	i, j, k, p, temp
+int	lv[LOGPTR], uv[LOGPTR], pivot
+define	swap {temp=$1;$1=$2;$2=temp}
+int	strcmp()
+
+begin
+	lv[1] = 1
+	uv[1] = nstr
+	p = 1
+
+	while (p > 0) {
+	    if (lv[p] >= uv[p])			# only one elem in this subset
+		p = p - 1			# pop stack
+	    else {
+		# Dummy do-loop to trigger optimizer.
+		do p = p, ARB {
+		    i = lv[p] - 1
+		    j = uv[p]
+
+		    # Select as the pivot the element at the middle of the
+		    # subfile; move it to the end of the range so that the
+		    # for loops below do not have to skip over it.  Selecting
+		    # a pivot near the center of the subfile helps prevent
+		    # quadratic behavior when sorting an already sorted array.
+
+		    k = (lv[p] + uv[p]) / 2
+		    swap (x[j], x[k])
+		    pivot = x[j]
+
+		    while (i < j) {
+			for (i=i+1;  strcmp (sb[x[i]], sb[pivot]) < 0;  i=i+1)
+			    ;
+			for (j=j-1;  j > i;  j=j-1)
+			    if (strcmp (sb[x[j]], sb[pivot]) <= 0)
+				break
+			if (i < j)		# out of order pair
+			    swap (x[i], x[j])	# interchange elements
+		    }
+
+		    j = uv[p]			# move pivot to position i
+		    swap (x[i], x[j])		# interchange elements
+
+		    if (i-lv[p] < uv[p] - i) {	# stack so shorter done first
+			lv[p+1] = lv[p]
+			uv[p+1] = i - 1
+			lv[p] = i + 1
+		    } else {
+			lv[p+1] = i + 1
+			uv[p+1] = uv[p]
+			uv[p] = i - 1
+		    }
+
+		    break
+		}
+
+		p = p + 1			# push onto stack
+	    }
+	}
+end