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

Malte Skarupke explains how to generalize radix sort to sort almost any data type and shares optimizations to make it faster than standard comparison sorts.

cppnow.org — Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/boostcon/cppnow_presentations_2017 — 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: BashFilms.com --- *--* ---