[plt-scheme] (Slightly Off) Looking for a Sorting Algorithm

> > The reason I need this is that my comparison function depends on the
> > relative position of the elements compared to each other and possibly
> > to other elements in the list.

Hi Erich,

If I'm understanding your requirement properly, I think one way to do this
is to just say that the elements that we are sorting are the indices
themselves.  For example:

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

(define names (list "bob" "mary" "josh" "alice"))
(define indices '(0 1 2 3))

(define sorted-indices
  (mergesort indices (lambda (i j)
		       (string<=? (list-ref names i)
				  (list-ref names j)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

That is, the elements stay stable, and we're sorting the indices instead.
Your less-than comparator can be be designed to be aware about the
relative position of things, since it's given 'i' and 'j'.