Question

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.)

Answer 1

Answer:

Quick sort and Merge sort supports parallelism

Explanation:

When we talk about parallelism, we are referring to the idea of breaking down a problem into a number of many subproblems after which we combine the solutions of these subproblems into a single solution. Here we allocate these subtasks to the multicore processors where each core gets assigned each of the subtasks are assigned to a core according to its ability or functionality. After each of the core are through with its evaluation, all their results are collated and combined to come up with a full rounded and complete solution to the given problem.

If we take a look at sorting algorithms such as selection sort, bubble sort and insertion sort, we will find out that these algorithms cant be simulated on a multicore processor efficiently because they are sequential algorithms.

On the other hand, we have sorting algorithms that can easily be simulated in a multicore processor since they can divide the given problem into subproblems to solve after which the solutions can be combined together to arrive at or come up with a complete solution to the problem. This algorithms includes Quick sort and Merge sort, they make use of Divide and Conquer paradigm.