This event has ended. View the official site or create your own event → Check it out
This event has ended. Create your own
View analytic
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 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

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

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

Attendees (16)