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 

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

Leave a Reply

Your email address will not be published. Required fields are marked *