## Marriage Sort

### August 20, 2010

Here is our version of marriage sort:

`(define (msort! lt? vec) ; marriage sort`

(define (v i) (vector-ref vec i))

(define (v! i x) (vector-set! vec i x))

(define (swap! i j) (let ((t (v i))) (v! i (v j)) (v! j t)))

(let* ((end (- (vector-length vec) 1))

(skip (if (positive? end) (isqrt end) -1)))

(while (<= 0 skip)

(let ((vbest 0) (i 1))

(while (< i skip)

(when (lt? (v vbest) (v i)) (set! vbest i))

(set! i (+ i 1)))

(while (< i end)

(if (lt? (v vbest) (v i))

(begin (swap! i end) (set! end (- end 1)))

(set! i (+ i 1))))

(swap! vbest end)

(set! end (- end 1))

(set! skip (if (positive? end) (isqrt end) -1)))))

(isort! lt? vec))

The outer `while`

controls the recursive sweeps, the first of the inner `while`

s finds the largest value in the sample, and the second of the inner `while`

s moves large values to the end of the array; the final `swap!`

moves the largest sample value just before the new end. The three pointers are named `skip`

, `end`

and `i`

; `vbest`

points to the largest value in the sample. Here is `isort`

:

`(define (isort! lt? vec) ; insertion sort`

(define (v i) (vector-ref vec i))

(define (v! i x) (vector-set! vec i x))

(define (swap! i j) (let ((t (v i))) (v! i (v j)) (v! j t)))

(let ((n (vector-length vec)))

(do ((i 0 (+ i 1))) ((= i n))

(do ((j i (- j 1)))

((or (<= j 0) (< (v (- j 1)) (v j))))

(swap! (- j 1) j)))))

We used `isqrt`

, `when`

and `while`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/4Sldvq9Q. You might also enjoy a solution in Factor by John Benediktsson, who sometimes posts his solutions here at Programming Praxis, and from whom this post was stolen.

Here’s a ruby version translated straight from the pseudo-code with “last” substituting for “end”. I took the insertion_sort straight from the wikipedia pseudo-code.

My C++ solution:

oops, insertion_sort (array, array+SIZE); should be marriage_sort (array, array+SIZE);

I wrote a Factor version:

http://re-factor.blogspot.com/2010/08/marriage-sort.html