## 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.

Pages: 1 2

### 4 Responses to “Marriage Sort”

1. slabounty said

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.

```class Array
def swap(i, j)
self[i], self[j] = self[j], self[i]
end

def marriage_sort!
last = self.length
while true
skip = Math.sqrt(last).to_i - 1
break if skip <= 0

# Pick the best element in the first vN - 1:
best_pos = 0; i = 1
while i < skip
best_pos = i if self[i] > self[best_pos]
i += 1
end

# Now pull out elements >= self[bestPos], and move to the end:
i = skip
while i < last
if self[i] >= self[best_pos]
self.swap(i, last-1)
last -= 1
else
i += 1
end
end

# Finally, move our best pivot element to the end
self.swap(best_pos, last-1)
last-=1
end

# Finish off with insertion sort to put the elements into true sorted order
self.insertion_sort!
end

def insertion_sort!
self.each_index do |i|
v = self[i]
j = i-1
done = false
begin
if self[j] > v
self[j+1] = self[j]
j = j-1
done = true if j < 0
else
done = true
end
end while done == false
self[j+1] = v
end
self
end
end

a = [5, 7, 8, 10, 3, 2, 9, 4, 6, 1]
p a.marriage_sort!
```
2. zcbenz said

My C++ solution:

```#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

void insertion_sort (int *begin, int *end) {
int *itr = begin+1;
while (itr < end) {
int save = *itr;
int *current = itr;
while (current > begin) {
if (save < *(current-1))
*current = *(current-1);
else
break;
--current;
}

*current = save;
++itr;
}
}

void marriage_sort (int *begin, int *end) {
int *oend = end;
int *skip = begin + (size_t)sqrt (end - begin);
if (skip <= begin) return;

int *maxi = max_element (begin, skip);
while (skip < end) {
if (*skip > *maxi) swap (*skip, *--end);
++skip;
}
swap (*maxi, *--oend);

insertion_sort (begin, end);
}

int main(int argc, char *argv[])
{
srand (time (NULL));
const size_t SIZE = 16;
int array[SIZE];

generate (array, array+SIZE,
[]() { return rand()%40; });
for_each (array, array+SIZE,
[](int n) { cout << n << " "; });
cout << endl;

insertion_sort (array, array+SIZE);
for_each (array, array+SIZE,
[](int n) { cout << n << " "; });

return 0;
}
```
3. zcbenz said

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