Sorting networks

Sorting networks, a talk delivered by Kofi Wilkinson on 16th November 2022 Abstract: We all know about common "optimal" sorting methods such as mergesort and quicksort, and the O(n log n) time complexity bound that these comparison-based routines yield, but very few are aware of the speed-up opportunities that sorting networks provide us. By harnessing the power of instruction-level parallelism, sorting networks allow us to pull the O(n log n) bound for comparison-based sorting towards a sub-linear O((log n)^2).