for review: new predicates in map.m

[Bert Thompson]

Peter Schachte <pets at cs.mu.OZ.AU> writes:

|On Wed, Oct 21, 1998 at 11:41:20PM +1000, Andrew Bromage wrote:
| > Simplest way to do that is basically to split the list into ascending
| > and descending runs, merge each adjacent ascending and reversed-
| > descending runs, then bottom-up merge the runs that you get.

|That's what SAM sort does.

It's really just a small variation on Natural Mergesort, an algorithm that's
been around for ages. I naively `invented' it in the halcyon days of
Gofer version 0.x, only later to discover Knuth (I think) had already
done it and given it a name.

The fastest Gofer sort I managed to write was a natural mergesort that merges
both ascending and descending runs, merges them in a balanced manner with
the reverse runs merged separately from the ascending ones, and switches
to insertion sort for short lists.

A similar kind of sort would work well in Mercury.

Bert