// S C V S O R T -- SCAN CONVERTER    (PREPRESS)
// catalog number ???

// Sort  routine for scan conversion

get "scv.dfs"

// outgoing procedures
external
[
QuickSort
]

// outgoing statics
//external
//	[
//	]
//static
//	[
//	]

// incoming procedures
//external
//	[
//	]

// incoming statics
//external
//	[
//	]

// internal statics
//static
//	[
//	]

// File-wide structure and manifest declarations.

// Procedures

let

//QuickSort: sort an array of double words. Knuth v.3 p. 116.
//	Comparison test is: first word first, then second word
//	(This is like a two-character key, not like a double-precision
//	number.)
// b=> the array.
// n=number of elements to sort (not counting guards). n<32000
//    (i.e. first element is in b!2 and b!3, last in b!(2n) and b!(2n+1)
// 2 words	- infinity
// 2n words	intersections
// 2 words	+ infinity

QuickSort(b,n) be [
let n2=n lshift 1
let b1=b+1
b!0=minusinfinity	//Negative guard
b!(n2+2)=plusinfinity	//Positive guard
let stack=vec 20; let stack1=vec 20
let stptr=0		//Quicksort stack.
let l=2			//Q1
let r=n2		//set left,right
let i,j,k,k1=nil,nil,nil,nil
[							//Q2
test r-l gr 20 then
[
i=l; j=r
k=b!l; k1=b1!l
[					//Q3
while k ls b!j %
(k eq b!j & k1 ls b1!j) do j=j-2
if j le i then [ b!i=k; b1!i=k1; break ] //Q4
b!i=b!j; b1!i=b1!j; i=i+2
while b!i ls k %			//Q5
(b!i eq k & b1!i ls k1) do i=i+2
if j le i then [ b!j=k; b1!j=k1; i=j; break ] //Q6
b!j=b!i; b1!j=b1!i; j=j-2
] repeat
test r-i ge i-l then			//Q7
[ stack!stptr=i+2; stack1!stptr=r; r=i-2 ]
or
[ stack!stptr=l; stack1!stptr=i-2; l=i+2 ]
stptr=stptr+1
]
or
[					//Q8
for j=l+2 to r by 2 do
[
k=b!j; k1=b1!j; i=j-2
while b!i gr k %
(b!i eq k & b1!i gr k1) do
[
let i2=i+2
b!i2=b!i
b1!i2=b1!i
i=i-2
]
let i2=i+2
b!i2=k; b1!i2=k1
]
if stptr eq 0 then break		//Q9
stptr=stptr-1
l=stack!stptr; r=stack1!stptr
]
] repeat
]