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

71–80 of 110 posts

Re: Quadsort: a stable non-recursive merge sort

#71

Post by mcherm »

thdespou wrote: post #69

I'm a bit sceptical because I don't see any mathematical proof. Only benchmarks which do not prove a lot. It may be faster only by a constant factor on a particular machine but for sufficiently large n it would be as fast as mergesort. 1000000 is peanuts. We need to see convergence for about billions+ of numbers.

No one is claiming that this sort algorithm (or any other) is asymptotically faster than O(n log(n)). It can be mathematically proved that no sort algorithm can improve on this. The object with sort algorithms is to find one with good constant-factor performance on typical inputs.

Frankly, I am more persuaded by the arguments in favor of an algorithm like "Tim-sort", which doesn't claim to micro-optimize hardware more efficiently (that's basically what "better swapping" is claiming), but instead claims that the algorithm is particularly efficient on some commonly-seen patterns (like "partially-sorted", or "pieces of the list are reverse-sorted"). Of course, any kind of argument about why one sort is better than another are inferior to actual benchmarks.

Re: Quadsort: a stable non-recursive merge sort

#72

Post by klyrs »

namdnay wrote: post #70
darawk wrote: post #64

Earlier quoted context omitted.

A radix sort is a type of hashing, no? You're bucketing the items based on a reduced form projection of them onto some smaller subspace.

I think it's different in that you don't care what the output of a hash is, as long as it's sufficiently unique or whatever. Whereas here the buckets are are intimately tied to the input. It's more of an arithmetic hack I'd say, as it only works on decimal numbers

Radix sort works in any base

Re: Quadsort: a stable non-recursive merge sort

#73

Post by nwellnhof »

xucheng wrote: post #16

Quick sort is not the fastest sorting algorithm. It would be nice if there is a benchmark comparing with other state of the art algorithms like Timsort.

It depends on the implementation but Quicksort typically beats Timsort with random data. Quicksort is unstable though, so that's not a fair comparison.

Re: Quadsort: a stable non-recursive merge sort

#74

Post by amcsi »

mcherm wrote: post #71
thdespou wrote: post #69

I'm a bit sceptical because I don't see any mathematical proof. Only benchmarks which do not prove a lot. It may be faster only by a constant factor on a particular machine but for sufficiently large n it would be as fast as mergesort. 1000000 is peanuts. We need to see convergence for about billions+ of numbers.

No one is claiming that this sort algorithm (or any other) is asymptotically faster than O(n log(n)). It can be mathematically proved that no sort algorithm can improve on this. The object with sort algorithms is to find one with good constant-factor performance on typical inputs. Frankly, I am more persuaded by the arguments in favor of an algorithm like "Tim-sort", which doesn't claim to micro-optimize hardware mor…

I'm quite a noob, and this is a bit off-topic, but if it's mathematically proven that no sorting algorithm can be faster then O(n*log(n)), but we know for sure that checking if an array is sorted is O(n), then doesn't that prove that P ≠ NP?

Re: Quadsort: a stable non-recursive merge sort

#75

Post by nightcracker »

vhvjkyhkogvv wrote: post #67
nightcracker wrote: post #63

C's qsort() is notoriously bad because the comparison function isn't inlined, meaning the majority of time is spent in call overhead. Zhangxp1998 ported quadsort to C++ and compared with std::sort and found it to be slower: https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... Shameless self promotion, if you want a faster sorting implementation, check out pdqsort ( https://github.com/orlp/pdqsort ) which i…

Comparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.

That is a fair point, I missed that quadsort is claimed to be stable.

Re: Quadsort: a stable non-recursive merge sort

#76

Post by stkdump »

darawk wrote: post #64
stkdump wrote: post #62

Earlier quoted context omitted.

Small nitpick: radix sort has nothing to do with hashing.

A radix sort is a type of hashing, no? You're bucketing the items based on a reduced form projection of them onto some smaller subspace.

Radix sort (similar to bucket sort) groups items based on individual digits of the non-hashed values. If you hash the values before, you will end up with the data being sorted according to their hash, but they will appear almost random in their unhashed form.

Re: Quadsort: a stable non-recursive merge sort

#77

Post by seanhunter »

chkas wrote: post #59
simias wrote: post #56

Earlier quoted context omitted.

Sorting sorted or mostly-sorted arrays is not uncommon in many use cases.

"Mostly-sorted" is a very vague definition.

Usually what people mean by mostly sorted in CS is that there is some small K such that each element in the input is no more than K places from the position it would be in if the input was sorted.

Re: Quadsort: a stable non-recursive merge sort

#78

Post by davuinci »

mcherm wrote: post #71
thdespou wrote: post #69

I'm a bit sceptical because I don't see any mathematical proof. Only benchmarks which do not prove a lot. It may be faster only by a constant factor on a particular machine but for sufficiently large n it would be as fast as mergesort. 1000000 is peanuts. We need to see convergence for about billions+ of numbers.

No one is claiming that this sort algorithm (or any other) is asymptotically faster than O(n log(n)). It can be mathematically proved that no sort algorithm can improve on this. The object with sort algorithms is to find one with good constant-factor performance on typical inputs. Frankly, I am more persuaded by the arguments in favor of an algorithm like "Tim-sort", which doesn't claim to micro-optimize hardware mor…

To be precise, we can prove that no sort comparison-based algorithm can do better than O(n log(n)) comparisons. There are some variations though that do better than that, though they are not based on comparisons (i.e counting sort, radix sort).

Re: Quadsort: a stable non-recursive merge sort

#79

Post by C4stor »

amcsi wrote: post #74
mcherm wrote: post #71

Earlier quoted context omitted.

No one is claiming that this sort algorithm (or any other) is asymptotically faster than O(n log(n)). It can be mathematically proved that no sort algorithm can improve on this. The object with sort algorithms is to find one with good constant-factor performance on typical inputs. Frankly, I am more persuaded by the arguments in favor of an algorithm like "Tim-sort", which doesn't claim to micro-optimize hardware mor…

I'm quite a noob, and this is a bit off-topic, but if it's mathematically proven that no sorting algorithm can be faster then O(n*log(n)), but we know for sure that checking if an array is sorted is O(n), then doesn't that prove that P ≠ NP?

No it doesn't, since O(n*log(n)) is in P too. P = NP doesn't imply that the complexity of finding the solution has the exact same complexity than verifying it, just that both are polynomial.

Re: Quadsort: a stable non-recursive merge sort

#80

Post by level3 »

klyrs wrote: post #72
namdnay wrote: post #70

Earlier quoted context omitted.

I think it's different in that you don't care what the output of a hash is, as long as it's sufficiently unique or whatever. Whereas here the buckets are are intimately tied to the input. It's more of an arithmetic hack I'd say, as it only works on decimal numbers

Radix sort works in any base

Radix sort also works on strings, etc. (anything that can be lexicographically ordered)
Post reply on HN