# Algorithms Summary Points – Part 4: MergeSort, Proving Recursive Algorithms

This note has some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick note or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first.  Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of help.

## Merge Sort, Proving Recursive Algorithms

### Merge Sort

• Uses divide and conquer – Recursion
• It splits the input array into two nearly equal halves recursively
• Returns an array once the number of elements in it is 1 – This is the base case
• Then it merges each pair of halves in sorted order.
• It is stable
• Running time is O(n log n)   –  because we divide into halves like in binary search, we perform log n self-calls. Every level will sum up to n operations when merging (since merging is O(n)), which is how we get O(n log n)
• Worst Case – O(n log n)
• Best Case – O(n log n)
• Average Case O(n log n)
• In all cases, it still does the recursion and merging
• It is not inversion bound.

## Proving Recursive Algorithms

1. To prove that a recursive algorithm is correct, we check 3 things:
2. There is a base case, and the self-calls lead to the base case.
3. The base case is correct
4. The recursive steps are correct