Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quadsort: a stable non-recursive merge sort

github.com

Post reply on HN
Print view View original

41–50 of 110 posts

Re: Quadsort: a stable non-recursive merge sort

#41

Post by thaumaturgy »

csense wrote: post #30
thaumaturgy wrote: post #19

Earlier quoted context omitted.

It isn't. Sorting networks ( https://en.wikipedia.org/wiki/Sorting_network ) provide the best possible in-place sorting combinations for N elements, where N is currently At lazy glance, it looks kind of like Quadsort has re-derived a variation of the 4-element sorting network.

> If somebody could find a way to generalize the sorting network algorithm for any number of input elements In section 2 in that Wikipedia article, it links to many constructions that do exactly that. A couple are O(n log(n)), but complicated and impractical. The algorithms people use are O(n log^2(n)) ones. FWIW, sorting networks are data-independent . I.e. for any input, you always compare-and-swap the same element…

I was imprecise. I was talking about the construction of optimal sorting networks. You're correct to point out that there are several approaches now for constructing sorting networks for arbitrary numbers of inputs, but as noted in that section, they all have some very important tradeoffs. I said, "...provide the best possible in-place sorting combinations for N elements, where N is currently "For one to eleven inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉. The first ten optimal networks have been known since 1969, with the first eight again being known as optimal since the work of Floyd and Knuth, but optimality of the cases n = 9 and n = 10 took until 2014 to be resolved.[11] An optimal network for size 11 was found in December of 2019 by Jannis Harder..."

Clearly I also should've said < ~12.

Re: Quadsort: a stable non-recursive merge sort

#42

Post by chalst »

jph wrote: post #6

Summary: this is a non-recursive merge sort with improvements. Benchmark of quadsort() versus C qsort(): * ~10x faster on forward-order items * ~2x faster on reverse-order items * ~equivalent on random-order items Improvements: * Ordering: when blocks of items are in order, or in reverse-order, then do special case handling, which gives quadsort O(n + log n) instead of qsort O(n * log n). * Boundaries: compare data r…

Good summary. Quibble: O(n + log n) = O(n).

Re: Quadsort: a stable non-recursive merge sort

#43

Post by senderista »

proc0 wrote: post #8

Interesting, but I'm surprised if this is the first time we have sorting algorithm that is swapping more than two elements at a time. I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested.

If you think about it, the "quadswap" is just unrolled merge sort on 4 elements.

Re: Quadsort: a stable non-recursive merge sort

#44

Post by kzrdude »

proc0 wrote: post #8

Interesting, but I'm surprised if this is the first time we have sorting algorithm that is swapping more than two elements at a time. I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested.

GrailSort (GitHub) and related they swap blocks at a time, isn't that a precedent?

Re: Quadsort: a stable non-recursive merge sort

#45

Post by kannmig »

chalst wrote: post #42
jph wrote: post #6

Summary: this is a non-recursive merge sort with improvements. Benchmark of quadsort() versus C qsort(): * ~10x faster on forward-order items * ~2x faster on reverse-order items * ~equivalent on random-order items Improvements: * Ordering: when blocks of items are in order, or in reverse-order, then do special case handling, which gives quadsort O(n + log n) instead of qsort O(n * log n). * Boundaries: compare data r…

Good summary. Quibble: O(n + log n) = O(n).

I think OP made the distinction intentional to “show their working”, so to speak.

Re: Quadsort: a stable non-recursive merge sort

#46

Post by hinkley »

xeeeeeeeeeeenu wrote: post #35

In his benchmark, the author is assuming that qsort() is implemented using quicksort, but that's not necessarily true. For example, glibc is using mergesort (although it falls back to quicksort if the system is short on memory).

I can’t imagine the sort of bugs you get when your code relies on stable sort but calls qsort and everything works great until the machine is under heavy load.

Re: Quadsort: a stable non-recursive merge sort

#48

Post by alexchamberlain »

zhangxp1998 wrote: post #14

qsort has to invoke your comparison function repeatedly, which incurs a lot of overhead. Try C++'s std::sort

This feels a little unfair; the function is invoked the same number of times, but C++ has a mechanism for removing the overhead of calling a function (inlining).

Re: Quadsort: a stable non-recursive merge sort

#50

Post by ummonk »

dpbriggs wrote: post #28
N3XT wrote: post #15

Earlier quoted context omitted.

From the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.

Swap space is allocated here: https://github.com/scandum/quadsort/blob/c3bcf139c59eb296b28...

Okay, that looks like it is proportional to the size of the array, so definitely not in-place.
Post reply on HN