[plt-scheme] stable sort

I raised this issue earlier:

http://list.cs.brown.edu/pipermail/plt-scheme/2004-July/006075.html

There is one issue with defining a sort to be stable: one's intuition 
would indicate that you need to specify in the interface to the sort 
whether it takes a reflexive or an irreflexive relation.  This 
intuition may be wrong; I've managed to convince myself that you can 
hack around your lack of knowledge of whether a relation is reflexive 
or irreflexive, as long as it acts in a consistent manner.

I believe that the following reimplementation of mergesort is stable, 
though I have not proven it to be so.
It is also a little less efficient than the current implementation of 
mergesort in mzlib (it makes some extra calls to the comparator)

   (define mergesort/stable
     (polymorphic
      (lambda (alox less-than)
        (letrec ([split (lambda (alox r)
			 (cond
			  [(null? alox) r]
			  [(null? (cdr alox)) (cons alox r)]
			  [else (split (cdr alox) (cons (list (car alox)) r))]))]
		[merge (lambda (l1 l2 r)
			 (cond
			  [(null? l1) (append! (reverse! r) l2)]
			  [(null? l2) (append! (reverse! r) l1)]
			  [(and (less-than (car l2) (car l1))
                                 (less-than (car l1) (car l2)))
                            (merge l1 (cdr l2) (cons (car l2) r))]
			  [(and (not (less-than (car l2) (car l1)))
                                 (not (less-than (car l1) (car l2))))
                            (merge l1 (cdr l2) (cons (car l2) r))]
			  [(less-than (car l1) (car l2))
			   (merge (cdr l1) l2 (cons (car l1) r))]
			  [else (merge l1 (cdr l2) (cons (car l2) r))]))]
		[map2 (lambda (l)
			(cond
			 [(null? l) '()]
			 [(null? (cdr l)) l]
			 [else (cons (merge (car l) (cadr l) null)
				     (map2 (cddr l)))]))]
		[until (lambda (l)
			 (if (null? (cdr l))
			     (car l)
			     (until (map2 l))))])
	 (if (null? alox)
	     null
	     (until (split alox null)))))))

On Nov 19, 2004, at 12:36 PM, Shriram Krishnamurthi wrote:

>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> There's no stable sort available?  I searched for "sort" in Help Desk
> and got
>
> (sort less-than?-proc list) PROCEDURE
> This is the same as mergesort (see section 21) with the arguments
> reversed.
>
> (mergesort list less-than?) PROCEDURE
> Sorts list using the comparison procedure less-than?. This
> implementation is not stable (i.e., if two elements in the input are
> ``equal,'' their relative positions in the output may be reversed).
>
> (quicksort list less-than?) PROCEDURE
> Sorts list using the comparison procedure less-than?. This
> implementation is not stable (i.e., if two elements in the input are
> ``equal,'' their relative positions in the output may be reversed).
>
> S.
>

----
"i'm always going to refer to him as rmfs from now on"
  -josh