Week 4 Merge Sort and Midterm

This week in Design and Analysis of Algorithms we focused primarily on one of the divide and conquer algorithms for sorting known as Merge Sort, and additionally we also had our midterm. The divide and conquer technique is quite interesting to me, it essentially provides a way to break down problems into simpler manageable pieces. In other words it focuses on solving the problem by dividing it into smaller pieces and then combining the solutions of those to form the final result to the main problem. The main algorithm we studied using this technique was the Merge Sort which was a nice first example and practical use for divide and conquer. The way merge sort works is that it divides an input array into two halves, and continues doing that recursively until there are sub-arrays that contain only one element. Afterwards the algorithm conquers by merging pairs of sorted sub-arrays together to form larger sorted arrays. It typically compares elements of each sub-array and places the smaller one into a new array and continues doing so until all the elements are merged in a sorted order. The time efficiency of the merge sort is O(n log n), the "log n" comes from the fact that the arrays are divided in half recursively, and the first "n" term comes from the merging/combination area of the code for each recursion call. The last thing I learned about Merge Sort came from a dev blog I posted in the class discord which discusses how this algorithm has a downside which was space complexity as it required more memory for each temporary array it creates during the merge. Overall this week provided some great insight into divide and conquer, and looking through the week 5 module we will take a look at a couple more divide and conquer algorithms. The lecture video and practice document made the algorithm easier to understand. In regards to the midterm I thought I did okay in it, definitely could have done better if I reread the problems thoroughly because some questions were missed due to me rushing through it for some reason. I'll definitely take note and read the problems slowly for the final, also the cheat-sheets that the class discord provided were very helpful. Other than that the week was quite short and informative. I learned quite a lot about recursive divide and conquer problems.