What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?

  • 1
    $\begingroup$ One example is QuickSelect. Another example is fast matrix multiplication. $\endgroup$ – Yuval Filmus Dec 3 '18 at 9:01
  • 1
    $\begingroup$ We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$ – Raphael Dec 3 '18 at 17:03
  • 2
    $\begingroup$ Also, one has to wonder if you've done any research on your own. Even Wikipedia has more examples! There are probably hundreds of examples in the literature. $\endgroup$ – Raphael Dec 3 '18 at 17:04

There are many algorithms that uses the divide-and-conquer paradigm besides merge sort and quicksort.

"There is no accepted formal definition of the divide and conquer paradigm, and so we must regard this paradigm as an informal concept.", reads an answer by Yuval Filmus. I will use Wikipedia entry on divide-and-conquer as the reference to interpret its meaning.

That Wikipedia entry mentions quite a few examples. Here are some of them.

As Raphael commented, there are probably hundreds of examples in the literature. Here are a few simple or notable ones.

We can also relate many structural decomposition techniques to divide and conquer. Whenever we are using the recursive nature of a tree graph, it could be considered an application of divide and conquer. Whenever we are using the Jordan blocks of a matrix, it could be considered likewise. When you reduce a problem about a graph to each of its connected component, it could be considered likewise. In this sense, divide-and-conquer appears even more pervasive.

There are also many examples that are better classified as decrease and conquer. Some notables of them are binary search, exponentiation by squaring, Johnson–Trotter algorithm that lists all permutations. Whether we or you would like to consider them as divide-and-conquer (proper) is up to our or your preferences. If you do, it may "help you conceptualize the algorithms that you learn in the course. If you don't find this helpful, just ignore it", says Yuval.

If you have plenty of time to kill, you may enjoy the following tedious exercise.

Exercise. Check which algorithms in the list of algorithms by Wikipedia use divide-and-conquer.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.