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
- 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