## Marriage Sort

### August 20, 2010

Today’s exercise is about a relatively new sorting algorithm. We start with an article Optimizing Your Wife by Kevin Brown, which proposes that the best way for a man to find a wife is to decide how many women he is willing to date before he chooses a wife, we’ll call that N, determine which of the first √N women is “best,” according to whatever matters to him, and then choose the next woman after the first √N that is better than any of the first √N women. For instance, to find the marriageable woman in a batch of a hundred, date ten of them, then marry the next one that is better than any of those ten. You may not find the optimal woman, but you’ll be close.

Eric Burnett turned Brown’s idea into a sorting algorithm. First, sample the first √N values at the beginning of an array, then swap any of the remaining values that are better than the greatest value of the sample to the end of the array, swap the greatest value of the sample just before those at the end, then recur on the smaller array before those greatest values. Finish the sort by performing insertion sort on the entire array; that will be quick, since most values are near their final positions.

Burnett’s algorithm requires three pointers: the current location of the end of the sample, the current location of the end of the array still under consideration, and a pointer that sweeps through the array. The time complexity is O(n1.5), which is similar to other sorting methods like shell sort and comb sort that have a first stage that nearly sorts the input followed by insertion sort to clean up the rest.

Your task is to write a function that sorts an array using marriage sort. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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);