Original HN discussion: http://news.ycombinator.com/item?id=1236686

Just for clarity: that's the original discussion of the "Marriage optimization" issue, not the sort algorithm.

(I'd hate to see somebody skip the sort application thinking it's dupe.)

This assumes the man decides. If you truly confine the joint agreement to one decision maker, you could drastically alter what goes into a man making his decision.

A factor of equality exponentially complicates this hypothesis.

This is an interesting motivation, but the algorithm itself isn't particularly novel -- it's more or less a Quick sort with a really bad way of selecting pivots.

Yes and no...it does use a pivot, true, but is a bit more distinct than just that. For one thing, it is iterative where quicksort is recursive, so it doesn't need any external storage for a stack.

hence the name.

Wouldn't a marriage sort compare different keys as time went on? It would start sorting on "hair color" at the start, then "wants kids" towards the end?

;)

How does this algorithm perform when processor cache is considered?

Upon first glance it seems that it might perform really well with N = cache_line_size / sizeof(T) so perhaps N = 16 for sorting ints?

What size array would be optimal for N = 16?

I think you may have misunderstood how the algorithm works. N is simply the number of items remaining in the working set, so over the course of the algorithm N goes from n to 0.

You might be thinking of when √n - 1 = 16, (i.e. the maximum size of the initial length the pivot is picked from is 16). In that case, n = 17*17, or 289.

Does that help?