.alone←declaration(expurgate)=0;
.if alone then start
.require "<altosource>ttydefs.pub" source!file
.end
.every heading (|SORTPKG|,|September 5, 1975|,{page})
.once center
SORTPKG -- A General-Purpose Sort Routine
.skip 3
The file SORTPKG.BR 
.expurgate 1;
(on Maxc as <ALTO>SORTPKG.BR; source is <ALTOSOURCE>SORTPKG.C) 
.end;
contains a pleasant little (1330 (decimal) words, plus buffers) sorting package. It must be loaded with ALLOC.BR 
.expurgate 1;
(on Maxc as <ALTO>ALLOC.BR; source is <ALTOSOURCE>ALLOC.SR)
.end;
, which is a storage allocator presented elsewhere in this document. It is activated thus:

.begin indent 5,10,10;
$|Sort(GetItem, PutItem, CompareItems, ExpectedItemSize, MaxItemSize, StackNeeds)|, where

$|GetItem| is a subroutine called with two parameters, $&Item& and $&MaxItemLength&. It is expected to find another item to sort, to place that item into the vector $&Item&, and to return as its value the length (in words) of the item. If the length (in words) of the item is greater than $&MaxItemLength&, then $|GetItem| is expected to punt. When the set of items to sort has been exhausted, $|GetItem| should return the value 0.

$|PutItem| is a subroutine called with two parameters, $&Item& and $&ItemLength&. $|Sort| will call $|PutItem| with one item after another in final sorted sequence. $&ItemLength& is the length (in words) of $&Item& (as revealed by $|GetItem|).

$|CompareItems| is a subroutine called with two parameters, $&Item1& and $&Item2&. It should return a positive number if $&Item1& is to be considered greater than $&Item2&; a negative number if $&Item1& is to be considered less than $&Item2&; and 0 if they are to be considered equal.

$|ExpectedItemSize|, an optional parameter, is the size (in words) of an average item. Its default value is 10. It is used to help partition available buffer storage into tree- and item-space.

$|MaxItemSize|, an optional parameter, is the size (in words) of the largest item which the sort routine might have to handle. Its default value is 1000. It is used in allocating a block of storage big enough to hold the largest item which $|GetItem| might produce.

$|StackNeeds|, an optional parameter, is the largest amount of stack space needed by $|GetItem|, $|PutItem|, or $|CompareItems| (and whomever they might call). Its default value is 1000. It is used to compute how much stack space can be used for sort buffers.

.end;
The sort routine starts off by doing a variant of heapsort. If the input ends before the heap is full, then the sort is finished. Otherwise three temporary files, named SORT.SCRATCH1, SORT.SCRATCH2, and SORT.SCRATCH3, are created, a polyphase merge is initiated using replacement selection for initial run formation, and the temporary files are deleted. In other words, it's pretty efficient and if there is room for three copies of your input on your disk then $|Sort| can do the sort.

If the file F.USER contains the names of the user's BCPL modules, then the following command (for example) will load the whole mess into an executable file:

	BLDR @F.USER@ SORTPKG ALLOC INITALTOIO