C++Now 2017 has ended
Back To Schedule
Thursday, May 18 • 9:00am - 10:30am
Sorting in less than O(n log n): Generalizing and optimizing radix sort

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.

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.

avatar for Malte Skarupke

Malte Skarupke

Malte is an AI programmer at Avalanche Studios in New York. In his free time he likes to optimize algorithms. He blogs at www.probablydance.com

Thursday May 18, 2017 9:00am - 10:30am MDT