da.heapsort.muf - heapsort a list


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.


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.


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


"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 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.


Deborah Pickett (<Ariel> on FDCMuck).