[HN Gopher] Gridsort: A stable sort faster than std:sort
       ___________________________________________________________________
        
       Gridsort: A stable sort faster than std:sort
        
       Author : signa11
       Score  : 31 points
       Date   : 2021-02-08 10:41 UTC (1 days ago)
        
 (HTM) web link (github.com)
 (TXT) w3m dump (github.com)
        
       | olliej wrote:
       | The license does make it incompatible with most/all? other open
       | source licenses
        
       | chrchang523 wrote:
       | Interesting work.
       | 
       | License is worth noting. I am considering an "#ifndef FREE_MARS"
       | std::sort/qsort fallback for any code I write that uses this.
        
       | Etheryte wrote:
       | This is a good reminder of just how young of a field compsci
       | still is. Sorting is one of those fundamental things you don't
       | usually think about these days in your day-to-day work. Unless
       | you're an academic, for most practical uses it's a solved
       | problem. Of course there are edge cases like sorting all of
       | Twitter and whatnot, but for most situations, that holds. It's
       | then both exciting and refreshing to see new work still being
       | done on these fundamentals, pushing the envelope where you
       | might've not even known there was anything left to push.
        
       | birdbrain wrote:
       | The concept is interesting, but I'm a little leery of the detail
       | that the benchmark performance reported is in each case "the best
       | run out of 100".
       | 
       | One can claim, thus, only that this sort method's near-best-case
       | performance is better than `std::sort`'s near-best-case
       | performance (at least at the, er, P01 level). That says little to
       | nothing about the modal or reasonably-bad-case (say, P95)
       | performance.
       | 
       | A comparison of median values would lend much more weight to the
       | claim that this method is "faster" than `std::sort`.
       | 
       | But a really good benchmark report would show the entire
       | histogram of performance for each method.
        
       | RcouF1uZ4gsC wrote:
       | While you get better performance, you do trade off for more
       | memory usage. std::sort is in-place and uses O(1) extra memory.
       | gridsort uses O(n) extra memory, where n is the number of
       | elements you are sorting.
        
         | olliej wrote:
         | you need to compare to std::stable_sort, not std::sort
        
       | nedoka wrote:
       | I double checked and it's indeed faster, up to 3x faster if the
       | data is partially sorted.
       | 
       | It uses O(n) aux memory so if std::sort were to use this it would
       | still need IntroSort as a fallback, but that's pretty much a non-
       | issue since std::stablesort already does the same.
        
         | richardwhiuk wrote:
         | How can stablesort use IntroSort if IntroSort is non-stable?
        
           | jsnell wrote:
           | They mean that std::stable_sort already needs an extra memory
           | buffer, and falls back to a different algorithm if that can't
           | be allocated.
        
       | shureluck wrote:
       | This is super cool!
        
       ___________________________________________________________________
       (page generated 2021-02-09 23:02 UTC)