from Hacker News

Sorting functions implemented in C as std qsort() format

by adembudak on 12/26/17, 9:52 AM with 11 comments

• by beeforpork on 12/27/17, 10:35 AM

  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.

• by rambojazz on 12/26/17, 9:37 PM

  Repo has no license.

• by rurban on 12/28/17, 1:47 AM

  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.

• by xiii1408 on 12/27/17, 12:45 AM

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