C++Now 2017: M. Skarupke “Sorting in less than O(n log n): Generalizing and optimizing radix sort"

http://cppnow.org
—
Presentation Slides, PDFs, Source Code and other presenter materials are available at: https://github.com/boostcon/cppnow_pr...
—
It is well known that sorting algorithms can be no faster than O(n log n). Except that for sorting integers, there is a sorting algorithm that can sort in O(n): Radix sort.

In this presentation I will explain how to generalize radix sort so that it can sort almost everything that std::sort can sort. I will also present an optimization to the inner loop of radix sort which makes this more than two times faster than std::sort for many inputs.

The interface for radix sort has to be slightly different than for comparison based sorting, so I will also go over how to make your old use case run with the new algorithm.
—
Hi, I'm an AI programmer at Avalanche Studios in New York. We make video games written in C++. In my spare time I write libraries and blog on www.probablydance.com
—
Videos Filmed & Edited by Bash Films: http://www.BashFilms.com
---

*--*

---