One factor in algorithm performance that we've not had a chance to speak much about this quarter, but one that is certainly relevant in practice, is parallelism, which refers to the ability to speed up an algorithm by doing more than one thing at once. Nowadays, with most personal laptop or desktop computers having multicore processors, and with many workloads running on cloud infrastructure (i. e., potentially large numbers of separate machines connected via networks), the ability to run an algorithm in parallel is more important than ever. Of course, not all problems can be parallelized to the same degree. Broadly, problems lie on a spectrum between two extremes. (In truth, most problems lie somewhere between these extremes, but the best way to understand what's possible is to know what the extremes are.)

Embarrassingly parallel problems are those that are composed primarily of independent steps that can be run in isolation from others and without respect to the results of the others, which makes them very easy to parallelize. Given n cores or machines, you could expect to run n steps simultaneously without any trouble.
Inherently serial problems are those whose steps have to be run sequentially, because the output of the first step makes up part of the input to the second step, and so on. Multiple cores or machines aren't much help for problems like this.
Now consider all of the sorting algorithms we learned about in our conversation about Comparison-Based Sorting. For which of the algorithms would you expect a multicore processor to be able to solve the problem significantly faster than a single-core processor would be able to solve it? For each of the ones that would benefit, briefly explain, in a sentence or two, why multiple cores would be beneficial. (There's no need to do any heavy-duty analysis here; we just want to see if you've got a sense of which might benefit from parallelism and why.)