divert(-1)
# @(#)Copyright (c), 1987, 1993 StatSci, Inc.  All rights reserved.
define(`PASS',`')
define(`PASSIVE',`define(`PASS',`$'`1')')
define(`TEST',`$1 $2 $3')
define(`FUNCTION',`define(`TEST',`fun($'`1,$'`3) $'`2 0')')
define(`SORT',`
integer iu(64),il(64),p,i,j,m,k,ij,l
if (n<1) return
i = 1
j = n
m = 1
repeat {
	if (i<j)
		go to 10
	repeat {
		m = m-1
		if (m==0)
			break 2
		i = il(m)
		j = iu(m)
		while (j-i>10) {
#  first order a(i),a(j),a((i+j)/2), and use median to split the data
			10  k = i
			ij = (i+j)/2
			t = a(ij)
			PASS( it = b(ij) )
			if (TEST(a(i),>,t)) {
				a(ij) = a(i)
				PASS( b(ij) = b(i) )
				a(i) = t
				PASS( b(i) = it )
				t = a(ij)
				PASS( it = b(ij) )
				}
			l = j
			if (TEST(a(j),<,t)) {
				a(ij) = a(j)
				PASS( b(ij) = b(j) )
				a(j) = t
				PASS( b(j) = it )
				t = a(ij)
				PASS( it = b(ij) )
				if (TEST(a(i),>,t)) {
					a(ij) = a(i)
					PASS( b(ij) = b(i) )
					a(i) = t
					PASS( b(i) = it )
					t = a(ij)
					PASS( it = b(ij) )
					}
				}
			repeat {
				l = l-1
				if (TEST(a(l),<=,t)) {
					tt = a(l)
					PASS( itt = b(l) )
					repeat {
#  split the data into a(i to l).lt.t, a(k to j).gt.t
						k = k+1
						if (TEST(a(k),>=,t)) {
							if (k>l)
								break 2
							a(l) = a(k)
							PASS( b(l) = b(k) )
							a(k) = tt
							PASS( b(k) = itt )
							break 1
							}
						}
					}
				}
			p = m
			m = m+1
#  split the larger of the segments
			if (l-i<=j-k) {
				il(p) = k
				iu(p) = j
				j = l
				}
			else {
				il(p) = i
				iu(p) = l
				i = k
				}
			}
		if (i==1)
			break 1
		i = i-1
		repeat {
			i = i+1
			if (i==j)
				break 1
			t = a(i+1)
			PASS( it = b(i+1) )
			if (TEST(a(i),>,t)) {
				k = i
				repeat {
					a(k+1) = a(k)
					PASS( b(k+1) = b(k) )
					k = k-1
					if (TEST(t,>=,a(k))) {
						a(k+1) = t
						PASS( b(k+1) = it )
						break 1
						}
					}
				}
			}
		}
	}
return
')
divert(0)
SCCS_ID(95444,`@(#)'sort.m 3.10 last edit 2/20/93 StatSci. From BASEFILE)
