If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Divide and conquer algorithms

The two sorting algorithms we've seen so far, selection sort and insertion sort, have worst-case running times of \Theta, left parenthesis, n, squared, right parenthesis. When the size of the input array is large, these algorithms can take a long time to run. In this tutorial and the next one, we'll see two other sorting algorithms, merge sort and quicksort, whose running times are better. In particular, merge sort runs in \Theta, left parenthesis, n, \lg, n, right parenthesis time in all cases, and quicksort runs in \Theta, left parenthesis, n, \lg, n, right parenthesis time in the best case and on average, though its worst-case running time is \Theta, left parenthesis, n, squared, right parenthesis. Here's a table of these four sorting algorithms and their running times:
AlgorithmWorst-case running timeBest-case running timeAverage-case running time
Selection sort\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis
Insertion sort\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis
Merge sort\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis
Quicksort\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis

Divide-and-conquer

Both merge sort and quicksort employ a common algorithmic paradigm based on recursion. This paradigm, divide-and-conquer, breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. Because divide-and-conquer solves subproblems recursively, each subproblem must be smaller than the original problem, and there must be a base case for subproblems. You should think of a divide-and-conquer algorithm as having three parts:
  1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
  2. Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
  3. Combine the solutions to the subproblems into the solution for the original problem.
You can easily remember the steps of a divide-and-conquer algorithm as divide, conquer, combine. Here's how to view one step, assuming that each divide step creates two subproblems (though some divide-and-conquer algorithms create more than two):
If we expand out two more recursive steps, it looks like this:
Because divide-and-conquer creates at least two subproblems, a divide-and-conquer algorithm makes multiple recursive calls.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

Want to join the conversation?

  • leafers seed style avatar for user Galina Sinclair
    What is the connection/difference between recursive algorithms, divide and conquer and dynamic programming?
    (11 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user thisisrokon
    Why balancing is necessary in divide and conquer?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Here's the idea (I've somewhat simplified it):

      Solving a divide and conquer problem will cost you:
      cost/level * number of levels

      If, each level, you break each sub problem into two equal sized chunks, then it will take log_2(n) levels before the sub problem size is broken into chunks of size 1.

      However, if you break each of the the sub problems into one big chunk and one small chunk, then it can take almost n levels before the sub problems are broken into chunks of size 1.

      So, dividing each of the sub problems evenly will cost you:
      log_2(n) * cost/level

      And, dividing each of the sub problems into a big chunk, and small chunk will cost you somewhere around:
      n * cost/level (which is much worse)

      So for something like quick sort (which using the idea of divide and conquer):
      It costs n per level
      When it divides the problem evenly into nearly halves, it runs in: O(n * log_2(n))
      When it divides the problem into a big chunk and small chunk, it runs in: O(n*n) i.e. O(n^2)

      Hope this makes sense
      (9 votes)
  • blobby green style avatar for user jain.jinesh220
    What type of problem can come in divide and conquer strategy?
    (4 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Jonathan Oesch
    Looking at the running time table, it would appear that merge sort is a bit more superior than quick sort. Would there be a reason to choose quick sort over merge sort (assuming you were familiar with both)?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user jamesmakachia19
    1. Give a divide and conquer algorithm to search an array for a given integer. a. The algorithm must solve the following problem: Input: A, an integer array and k an integer. Output: TRUE if there is an A[i] = k. b. Provide an explanation of how your algorithm works c. Formal pseudocode of the algorithm d. A proof that the algorithm is correct e. A symbolic runtime analysis of the algorithm
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Divide and conquer search(array):
      if array is single element:
      if target found:
      return true
      else:
      return false
      return Divide and conquer search(left half of array) || Divide and conquer search(right half of array)

      You search every element exactly once so it is O(n)
      (1 vote)
  • blobby green style avatar for user tylon
    Posting here really about the(just prior to this page) stage 2 Challenge Solve hanoi recursively (no place to put questions on that page).

    The questions asks the following:

    Make a recursive function call to move the disks sitting on top of the bottom disk on the fromPeg to the spare peg, i.e. move (numDisks - 1) disks to the spare peg.

    You can find the spare peg by using the getSparePeg function.

    A call to hanoi.getSparePeg(peg1,peg2) returns the remaining peg that isn't peg1 or peg2.

    The hint says this:

    // recursive case:

    var sparePeg = hanoi.getSparePeg(fromPeg, toPeg);
    solveHanoi();

    But despite all that, even though it only seems to ask for the solveHanoi() to be filled out with the parameters, it wont progress. Do I have to seperately declare the fromPeg, and toPeg, and assign them letters?

    Below is a rough stab at the code:

    var solveHanoi = function(numDisks, fromPeg, toPeg) {
    if (numDisks===0)
    {
    return;
    }
    };
    var fromPeg="A";
    var toPeg="B";
    var sparePeg = hanoi.getSparePeg(fromPeg,toPeg);
    //solveHanoi(5, "A","B");
    //Program.assertEqual(hanoi.isSolved("B"),true);
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Zulqarnainhameed
    Design a heap construction algorithm by applying divide and conquer strategy
    ??
    (0 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      put data in heap (not in heap order yet) and call heapifyRecursive on top node

      heapifyRecursive( node ) {
      if ( node == null ) {
      return;
      }

      //this is the divide and conquer step
      heapifyRecursive( left child);
      heapifyRecursive( right child );

      //this step merges the results together into a valid heap
      heapifyDown( node );

      }
      (1 vote)
  • aqualine seed style avatar for user Alexander Malena
    Alexander Malena-Is there a connection between dividing and conquer algorithms in terms of how they are both used?
    (0 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user dnithinraj
    Not understanding the code for base case for tower of hanoi problem. Please advise.
    (0 votes)
    Default Khan Academy avatar avatar for user