### NAME

da.heapsort.muf - heapsort a list
### SYNOPSIS

- Input parameters:
- S[0]: address of function to make comparisons.

S[1]: integer, number of items in list.

S[2] to S[S[1]+1]: list.
- Return value:
- S[0]: integer, number of items in list.

S[1] to S[S[1]]: list.

### DESCRIPTION

da.heapsort.muf is an implementation of the heapsort algorithm. It is
guaranteed worst-case time complexity of O(`n` log `n`)). This means that
for very large lists it will run faster than other sorting algorithms
such as bubble and shell sorts.
To sort a list, place the list, MUF-style, on the stack. That is,
place each element on the stack, then place an integer saying how many
elements you want to sort. Finally, give the address of the function
to make the comparisons. This is done by preceding the function name
with a single apostrophe (`'`

).

This comparison function should accept two list items, compare them in
whatever way it wants, and return 1 if S[0] is less than S[1] (the
elements are in the correct order), -1 if S[1] is less than S[0] (they
need to be swapped), otherwise zero (semantically equivalent to
returning 1; heapsort only cares that elements need to be
swapped).

Then call the macro `.heapsort-list`

.
The smallest item is nearest the top of stack.

### RETURN VALUE

The list is returned in sorted order, with the smallest element near the
top of stack. The size of the list is unchanged.
### EXAMPLES

```
"This" "Is" "a" "Sorting" "Example" 5 'stringcmp .heapsort-list
```

( stack is is "This" "Sorting" "Is"
"Example" "a" 5 )

: int-compare ( i i -- i ) > if -1 else 1 then ;

(...)

5 -1 45 8 30 2 6 'int-compare .heapsort-list

( stack is 45 30 8 5 2 -1 6 )

### BUGS

Heapsort is not order-preserving. That is, you cannot expect two
elements which compare equal to remain in their current order after
the sort is completed. This means that if you want to sort on several
fields you cannot sort repeatedly on different fields but must compare
on all fields in order for a pair of list items.
Heapsort has a fairly large inner loop so it tends to be slower on
small and medium lists than other sort algorithms. For medium to
large lists you may experience problems with the instruction limit.

Because the heap-building part of the algorithm is linear in the
number of elements to be sorted, it may overflow the instruction stack
on particularly large lists. However, lists that large probably will
not fit on the data stack anyway.

### AUTHOR

Deborah Pickett (<Ariel> on FDCMuck).