[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Extension to merge sort

A useful extension to the merge sort (on lists) would be to
extend to "predicate" to have four possible return values.
Recall that at each step two items a and b are yanked off
of two lists, and on the basis of the predicate one is stuffed
into an output list and the other is left on its original
input list for iteration.  The change would be:
(pred a b) =	()	a  b: output b, leave a behind
		FIRST	output a, and throw away b
		SECOND	output b, and throw away a
		other non-():	output a, leave b behind
The idea is that if the predicate determines that two items
are in some sense equal, it may want to just discard one and
leave the other in the sort.  This is good for eliminating
duplicates.  If it is not desired to change the semantics
of the SORT function, perhaps this new one could be called
SIFT or something.
Also, it would be convenient if MERGE were available as
a separate function.