Sorting functions implemented in C as std qsort() format | Hacker News Reader

Sorting functions implemented in C as std qsort() format

github.com

41 pointsadembudak11 comments

The overview table should list some important properties I find myself comparing when selecting a sort algo: (a) stack usage, (b) heap usage, (c) whether the algo is stable.

E.g., I am a big fan of heap sort, because the implementation is very simple, and non-recursive (O(1) stack), uses no heap, and has worst-case time O(log n). It is almost perfect, but it is not stable. Now, mergesort fixes that stability issue (and its implementation is usually also very simple), but is often recursive (like this implementation) and it usually requires 'malloc()', because it cannot easily be run in-place. In an overview list, this dilemma would be nicely visible.

Repo has no license.

That is a problem. Thankfully, the language in Github's terms of service mitigates this a bit, although it'd be still ideal for the author to add a license too:

"If you set your pages and repositories to be viewed publicly, you grant each User of GitHub a nonexclusive, worldwide license to use, display, and perform Your Content through the GitHub Service and to reproduce Your Content solely on GitHub as permitted through GitHub's functionality (for example, through forking)."

https://help.github.com/articles/github-terms-of-service/#4-...

I’ve never heard a less realistic / more cop-out licensing policy. You can reproduce it, but only on github. You can’t even clone it locally (as the license still applies to your fork).

It’s only there so you can’t sue GitHub for not detecting the lack of license and disabling the fork button.

There's nonprivate repositories with a disabled fork button?! I've never seen that. I didn't think it was possible to disable forking on github, I know that you can on bitbucket.

That’s my point :)

Author has now added the "Do What The Fuck You Want Public License" (v2) [0]

[0] https://github.com/p1v0t/Sort/blob/master/LICENSE.md

I would suggest public domain, if only for the fact that sorting algorithms don't really have much in the way of originality.

I wonder why the better sorting algos are never compared, like for small integer indices counting sort is linear, for larger indices radix sort is optimal and for parallel sorting there exist also special variants.

Very cool! The function pointers bother me a bit, but hey, I'm a C++ programmer, and maybe link-time optimization is there now.

I've grown to like the plain C version. It has a very modular interface (doesn't require the sorted items to implements a certain protocol, i.e. "operator<"), and doesn't compile new code for each new type. (Often code size is the most important).

I think the worst case I measured is a factor of 2 in std::sort vs qsort on bare integers. On larger types it will be less. That's acceptable to me. Sorting is seldom the bottleneck (it's only important to do sort in many situations).

Reply on news.ycombinator.com