4 ms·
Introducing: Marriage Sort
- duck 17y agoOriginal HN discussion: http://news.ycombinator.com/item?id=1236686 http://news.ycombinator.com/item?id=1236686
- michael_dorfman 17y agoJust 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.)
- cperciva 17y agoThis 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.
- sfphotoarts 17y agohence the name.
- EricBurnett 17y agoYes 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.
- jamesshamenski 17y agoThis 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.
- fleitz 17y agoHow 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?
- EricBurnett 17y agoI 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?
- mike463 17y agoWouldn'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? ;)