On Thu, Mar 13, 2014 at 11:06 AM, Mike McFadden <[email protected]> wrote:
> Hi, I used a paper called "Ratio based in-place stable merging" to > implement a hybrid stable sort algorithm, and have been validating the > results against stable_sort and inplace_stable_sort. What's interesting is > that it matches 80-90% of the speed of stable_sort with random data, is > much faster in many other cases, and does so while using O(1) memory. > Simply giving it more memory allows it to closely match stable_sort in > speed. And compared to inplace_stable_sort it's anywhere from 3-15x faster, > with random data being about 5x faster. > > I have fully documented the algorithm and have a C++ implementation > available here: > https://github.com/BonzaiThePenguin/WikiSort > > The underlying algorithm was vetted and proven back in 2008 (there's a > link to the published paper on the GitHub project page), and the simplified > version used here is constantly tested against existing algorithms for > correctness and speed, but toying with a core feature of libc++ is > obviously not something to be taken lightly so I'm hoping for some > additional vetting and consideration. > Looks interesting to me. You should be able to accelerate std::rotate by using the cache even if neither range fits within it (perform a gcd rotate, moving a cache-sized chunk of the data at a time). Incidentally, your current Rotate function is cheating. You can't use std::memcpy/std::memmove on objects of class type in general. > My ultimate goal would be to replace inplace_stable_sort at the very > least, and ideally stable_sort as well. Maybe including it as a separate > sort function for now would be wise? > > - Mike > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits > >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
