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