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 is less than S (the elements are in the correct order), -1 if S is less than S (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
The smallest item is nearest the top of stack.
"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 )
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.