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

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

## 1 thought on “Algorithms Summary Points – Part 4: MergeSort, Proving Recursive Algorithms”