## YoU CanT MaKE BuBBleSorT FaSTER With ASseMbLY

14/01/2020

In one of the classes I teach, we end up writing assembly language programs. And while I explain the (sometimes very relative) benefits of writing assembly language, I use bubble sort as an example where even carefully crafted assembly language doesn’t mean much: it’s a bad algorithm to start with.

YoU CanT MaKE BuBBleSorT FaSTER With ASseMbLY

Except that it’s not quite true.

## Foiled!

16/03/2010

QuickSort, due to Hoare, is one of the best comparison-based sorting algorithms around. There are a number of variations, but the vanilla QuickSort does a great job… most of the times.

Indeed, there are occasions where QuickSort leaves its expected $O(n \lg n)$ run-time to reach $O(n^2)$ run-time, its worst case. But what does it take to push QuickSort into its worst behaviour?