I was lucky to get an invite to this month’s ACCU London meet-up on the topic of sorting. Dietmar Kuhl hosted the presentation at the plush Bloomberg offices on Finsbury Circus. The talk brought together a sample of approaches to speeding up QuickSort:
- insertion sort
- sentinel partitioning
- hand-rolled sorting for small collections
Overall, these changes (and others) made an impressive improvements, such that the combined algorithm rivalled std::sort for sorting std::vectors of integer. However, the algorithm wasn’t as competitive for other important element types such as std::string.
Dietmar intended the talk to be accessible to all, rather than an in-depth presentation using advanced C++ techniques. I think it was a good example of how you can iterate and bring in multiple techniques to optimise an algorithm for a specific use case.
musingstudio 