A divide-and-conquer algorithm is one that solves a problem by:

• divides the problem into sub-problems,
• recursively solves these sub-problems using the same algorithm, and
• recombines these solutions to the sub-problems to create a solution to the larger problem.

The assumption is, of course, that at some point there are certain sub-problems that are trivial to solve.

Under some circumstances, such algorithms will solve problems in less time than it takes to solve the overall problem directly.

We will look at a number of examples:

Binary search

Suppose we are searching a sorted array to see whether or not it contains a specific target value, and if it does, to tell us which entry that target value is located.

If we searched through the list normally, it require us to start at the beginning, and to search each entry, which would require us to check up to all $n$ entries.

However, suppose we instead use the following algorithm:

• If the array length is $1$, then we only have to check that one entry.
• Otherwise, divide the array into two and check the middle entry:
• If this entry contains the target value, we are finished, and return that entry.
• If it is not, this tells us which half of the array to continue searching.

This algorithm requires us to search at most $\log_2(n)$ entries in a sorted array of capacity $n$, which is fast indeed. For example, to search an array of capacity one million, this algorithm need only check approximately 20 entries before returning a verdict.

Merge sort

Suppose you had two stacks of examinations, both of which are sorted. As you can imagine, it should be quite easy to create a single sorted pile of examinations out of the two piles: just look at the top two papers and determine which comes first.

This is the idea of merging two lists. Suppose we have two vectors of capacity $n_1$ and $n_2$, and we wish to merge them into a single vector of capacity $n_1 + n_2$:

bool is_sorted( std::vector<double> const &array );
void merge( std::vector<double> const &e;array1,
            std::vector<double> const &e;array2,
            std::vector<double> &e;result );

// Include a helper fucntion that ensures that the arrays are
// correctly sorted, both before and after the algorithm runs
bool is_sorted( std::vector<double> const &array ) {
    for ( std::size_t k{1}; k < array.size(); ++k ) {
        if ( array[k - 1] > array[k] ) {
            return false;
        }
    }

    return true;
}

void merge( std::vector<double> const array1,
            std::vector<double> const array2,
            std::vector<double> result ) {

    assert( is_sorted( array1 ) && is_sorted( array2 ) );
    
    // create an array of capacity equal to that of the 
    // two vectors being merged together
    int k{0}, k1{0}, k2{0};

    while ( (k1 < array1.size()) && (k2 < array2.size()) ) {
        if ( array1[k1] <= array2[k2] ) {
            result[k] = array1[k1];
            ++k1;
        } else {
            result[k] = array2[k2];
            ++k2;
        }

        ++k;
    }

    while ( k1 < array1.size() ) {
        result[k] = array1[k1];
        ++k1;
        ++k;
    }

    while ( k2 < array2.size() ) {
        result[k] = array2[k2];
        ++k2;
        ++k;
    }

    assert( k == result.size() );
    assert( is_sorted( result ) );
}

As you can see, if you double the capacity of both array1 and array2, you will approximately double the run time.

Now, to implement merge sort, we check if the vector capacity is zero or one, in which case, the vector is sorted. Otherwise, divide the vector into two, recursively call merge sort on the two, and then merge the results:

void merge_sort( std::vector<double> &array ) {
    if ( array.size() >= 2 ) {
        // Divide the vector into two, copying over the entries
        std::vector<double> array1(  array.size()/2 );
        std::vector<double> array2( (array.size() + 1)/2 );

        std::size_t k{0}, k1{0}, k2{0};

        while ( k1 < array1.size() ) {
            array1[k1] = array[k];
            ++k1;
            ++k;
        }

        while ( k < array.size() ) {
            array2[k2] = array[k];
            ++k2;
            ++k;
        }

        // Recursively call merge sort on the two arrays
        merge_sort( array1 );
        merge_sort( array2 );

        // Merge the two together again
        merge( array1, array2, array );

        assert( is_sorted( array ) );
    }
}

You can try this out at repl.it.

This is all there is. Now, for small arrays, this seems like a lot of overhead; however, as the arrays gets larger, the run time is significantly different from algorithms like insertion sort, selection sort, and (heaven forbid) bubble sort. To sort one million entries, it requires approximately 20 million comparisons and 40 million assignments. On the other hand, insertion sort would require on the order of half a trillion comparisons and assignments. Merge sort would be approximately ten thousand times faster.

The fast Fourier transform (FFT)

Normally, matrix-vector multiplication of an $n \times n$ matrix multiplied by an $n$-dimensional vector requires approximately $2n^2$ floating-point operations (FLOPs) or $6n^2$ FLOPs if we consider complex arithmetic. The unitary matrix used to calculate the frequencies in a vector, however, have a special shape that allows the entire process to be completed in $4n \ln(n)$ FLOPs. Thus, while normally finding the coefficients with respect to the oscillating basis vectors would require many more operations, in this special case, it can be found much more quickly. It actually requires $14 n \log_2(n)$ FLOPs.

For example, normally multiplying a $1000 \times 1000$ matrix and a $1000$-dimensional vector requires six million FLOPS, using the FFT can calculate this in $14 \times 20 \times 1000$ or less than three-hundred thousand FLOPs.

Karatsuba integer multiplication

To be completed...