# Merge Sort (Mar 22)

**Runtime complexity:** Θ(n log2 n)**Space complexity:** O(n) using arrays, O(log n) using linked lists

Merge sort is a fairly simple algorithm, and the short lecture notes reflect this. Despite its simplicity, merge sort is one of the more stable and efficient sorting algorithms, hence its popularity (along with QuickSort).

I recommend first reading through the lecture notes. Then go over to toptal for a great summary of merge sort, along with sample runs of merge sort. You can also click the button at the top of that page to compare merge sort with the other common sorting algorithms.

If you have trouble visualizing merge sort, give this visualization tool a try. Just select "Merge" from the top, then click Sort > Go in the bottle left corner. You can press Spacebar to pause the animation, then use left/right arrow keys to step through the process.

Merge sort is a *divide and conquer* algorithm, because it breaks the problem into smaller parts, solves each part, then combines the smaller solutions into a whole. Rather than just being recursive, it uses *multibranch recursion*, and then combines the answers back together.

**Step 1:** Divide into smaller parts, until the problem is trivial to solve (eg. size n = 1).**Step 2:** Combine the smaller solutions until you have solved the entire problem.

Stolen from Vineet Kumar at Wiki (jk, public domain, but always good to credit good work).

### Multi-threaded or Parallel Merge Sort

With enough threads/processors, you can reduce the run time complexity of merge sort to Θ(n), bottlenecked by the *merge* sub-algorithm. This can be further reduced to Θ(n / log^{2}_{ }n), by improving the *merge* sub-algorithm to O(lg_{2} n), using multithreaded merging with binary searches. Most details in your textbooks (CLRS 3ed., page 797).