# Divide and conquer algorithms

The basic idea behind merge sort is this: it tends to be a lot easier to sort two smaller, sorted lists rather than sorting a single large, unsorted one.

Hang on for a second — we’re programmers! Intrinsically we know that, at the end of the day, there really is no magic at play here. There’s something else going on under the hood, and it’s probably an abstraction of something else.

1. Divide and break up the problem into the smallest possible “subproblem”, of the exact same type.
2. Conquer and tackle the smallest subproblems first. Once you’ve figured out a solution that works, use that exact same technique to solve the larger subproblems — in other words, solve the subproblems recursively.
3. Combine the answers and build up the smaller subproblems until you finally end up applying the same solution to the larger, more complicated problem that you started off with!

# Spotting recursion in the (algorithm) wild

This is exactly what makes recursion so powerful: once we’ve figured out how to solve the problem of merging two lists together, it doesn’t matter if the list has one element, or a hundred — we can reuse the same logic in both scenarios.

# Recursion at work How recursion works inside of an implementation of a mergeSort function
1. a `merge` function, which actually combines two lists together and sorts them in the correct order
2. and a `mergeSort` function, which will continue to split the input array again and again, recursively, and will also call `merge` again and again, recursively.