[plt-scheme] stable sort

You can turn any unstable sort into a stable sort:

(require (lib "1.ss" "srfi"))		;iota

(define (unstable->stable sort)
  (lambda (l compare)
    (map car (sort (map cons l (iota (length l)))
		   (lambda (pair1 pair2)
		     (let ((x1 (car pair1)) (x2 (car pair2)))
		       (or (compare x1 x2)
			   (and (not (compare x2 x1))
				(< (cdr pair1) (cdr pair2))))))))))

(define strings '("this" "is" "a" "test"))
(define (first<? s1 s2)
  (char<? (string-ref s1 0) (string-ref s2 0)))

(require (lib "list.ss"))		;mergesort

(list (mergesort strings first<?)
      ((unstable->stable mergesort) strings first<?))
;; => (("a" "is" "test" "this") ("a" "is" "this" "test"))

Or is this a naive approach?

--dougo at place.org