How does a sorting network beat generic sorting algorithms?
But here we are not using the parallelization.
Modern CPUs can figure out when instructions are independent and will execute them in parallel. Hence, even though there's only one thread, the sorting network's parallelism can be exploited.
Where exactly does insertion sort make unnecessary comparisons?
The easiest way to see the extra comparisons is to do an example by hand.
Insertion sort:6 5 4 3 2 15 6 4 3 2 15 4 6 3 2 14 5 6 3 2 14 5 3 6 2 14 3 5 6 2 13 4 5 6 2 13 4 5 2 6 13 4 2 5 6 13 2 4 5 6 12 3 4 5 6 12 3 4 5 1 62 3 4 1 5 62 3 1 4 5 62 1 3 4 5 61 2 3 4 5 6Sorting network:6 5 4 3 2 16 4 5 3 2 15 4 6 3 2 14 5 6 3 2 1 # These three can execute in parallel with the first three4 5 6 3 1 2 #4 5 6 2 1 3 #4 5 6 1 2 31 5 6 4 2 31 2 6 4 5 31 2 3 4 5 61 2 3 4 5 6
The better question is why the sorting network only outperforms insertion sort (generally a very slow sort) by ~50%. The answer is that big-O is not so important when n is tiny. As for OP's question, Daniel has the best answer.