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.
Randall Munroe’s excellent Thing Explainer is on the shelves at
The author is probably more widely read as the illustrator of
Catching up on back issues of ACCU’s
This book is part of the SciFi MasterWorks series, so I had high expectations, especially as it was written by the lauded Philip K Dick. However, this book is different to others that I’ve read by him – it starts very slowly, seemingly in a normal family in a sleepy American town. Only much later does the plot encompass a more science fiction element, and a more sinister reason behind the daily puzzle that Ragle Gumm must complete is revealed.