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

31–40 of 110 posts

Re: Quadsort: a stable non-recursive merge sort

#31

Post by foota »

dhash wrote: post #26
foota wrote: post #13

Earlier quoted context omitted.

Nit: it's possible that there is a finite number of Pareto optimal sorting algorithms, and it may be possible to enumerate those.

Oh man if I could efficiently enumerate algorithms across the Pareto front of anything I’d be a happy camper. Procedures that enumerate Turing machines are generally very easy, or nigh impossible

You'd probably want to start by defining equivalence and then work from there. If your criteria for equivalence is loose enough you're already done, e.g., if you just look at runtime big O for randomized arrays or something you can't do better than n lg n so there's just the one Pareto optimal choice, with many possible implementations.

Re: Quadsort: a stable non-recursive merge sort

#32

Post by gizmo686 »

kccqzy wrote: post #20

This reminds me of a programming exercise I was asked to write when I first learned programming: write a sorting program generator that given N, generates a program that sorts an array of N elements optimally: the generated code has N! branches, one for each possible permutation. With some CSE help from the compiler, it can be really quite fast at the expense of code size. The author's explanation isn't entirely clea…

A program generator seems rather advanced for a beginner's assignment...

When I started, I wrote an Excel spreadsheet to generate what I would now describe as a 50 element array.

I also recall seeing a project to programatically generate mnemonic operators in Haskell, limited only by the ability of the compiler to not run out of memory. Sadly, I can't seem to find it.

Re: Quadsort: a stable non-recursive merge sort

#33

Post by kccqzy »

gizmo686 wrote: post #32
kccqzy wrote: post #20

This reminds me of a programming exercise I was asked to write when I first learned programming: write a sorting program generator that given N, generates a program that sorts an array of N elements optimally: the generated code has N! branches, one for each possible permutation. With some CSE help from the compiler, it can be really quite fast at the expense of code size. The author's explanation isn't entirely clea…

A program generator seems rather advanced for a beginner's assignment... When I started, I wrote an Excel spreadsheet to generate what I would now describe as a 50 element array. I also recall seeing a project to programatically generate mnemonic operators in Haskell, limited only by the ability of the compiler to not run out of memory. Sadly, I can't seem to find it.

> A program generator seems rather advanced for a beginner's assignment...

Ha, it's nothing more complicated than string concatenation.

Re: Quadsort: a stable non-recursive merge sort

#34

Post by thedance »

zhangxp1998 wrote: post #22
zhangxp1998 wrote: post #14

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

See https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... for a comparison of quadsort with C++'s std::sort. The compare functions are inlined.

Thanks for saving us the time. The punch line:

  Summarize: Slower than std::sort except on random tail.
Also a very important tidbit that std::sort is 10x faster than c's qsort for ordered inputs.

Re: Quadsort: a stable non-recursive merge sort

#36

Post by Naac »

Since we're already using O(N) space, it would be interesting to see how this compares to Radix sort[0], which is O(N) space but O(N) time ( due to just hashing everything ).

Like others have said, it would be cool to see quadsort stacked up to other current state-of-the-art sorting algorithms.

[0] https://en.wikipedia.org/wiki/Radix_sort

Re: Quadsort: a stable non-recursive merge sort

#37

Post by eru »

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…

If you have a k sorted (or reverse sorted) blocks, you can get O(n log k) performance in merge sort variants. Especially, if k is a small fixed constant, like 1 or 2 or 10, you should get linear performance.

A few language's standard library sorts implement that already.

For a serious implementation, of course, you not only care about the asymptotic performance, but also absolute runtimes.

Re: Quadsort: a stable non-recursive merge sort

#38

Post by eru »

foota wrote: post #31
dhash wrote: post #26

Earlier quoted context omitted.

Oh man if I could efficiently enumerate algorithms across the Pareto front of anything I’d be a happy camper. Procedures that enumerate Turing machines are generally very easy, or nigh impossible

You'd probably want to start by defining equivalence and then work from there. If your criteria for equivalence is loose enough you're already done, e.g., if you just look at runtime big O for randomized arrays or something you can't do better than n lg n so there's just the one Pareto optimal choice, with many possible implementations.

It depends on your model of computation.

O(n log n) is only the frontier for comparison based sorts that know nothing about the distribution of inputs.

If your sorting algorithm is allowed to do anything else on your data, like hashing or looking at bits or arithmetic, different lower bounds might apply.

Re: Quadsort: a stable non-recursive merge sort

#39

Post by eru »

QuinnWilton wrote: post #5

I've never seen a sorting algorithm that uses a non-binary comparison function to order values. Is that a novel technique? It seems really obvious in hindsight, so I'm sure there's just prior art I don't know about.

If tried that in eg Haskell to see if I can beat the standard library's highly optimized sort.

In theory, you can get O(n log k) performance, where k is the number of distinct elements (so k In practice, all my attempts were absolutely slower than the standard approach based on binary comparisons only. (But that's saying more about me than about the domain.)

Re: Quadsort: a stable non-recursive merge sort

#40

Post by [deleted] »

nneonneo wrote: post #18

How does this fare against Python's famous Timsort (used by several languages and systems)? How about the dual-pivot quicksort used by Java for primitive arrays? Someone has to have put together a nice benchmark for comparing many sorting algorithms. I wish that the author had done some benchmarking first, so that the proposed algorithm can properly be positioned w.r.t. state-of-the-art techniques.

[deleted]
Post reply on HN