Algorithms

Motivation Experiencing binary search was like a divine revelation of the ingenuity of algorithms. How can computer code be so clever and efficient at the same time? We don’t thank the inventors enough 😏. Among the great, simple, and everyday algorithms used is merge sort. It is a divide-and-conquer algorithm that works by taking a big problem, chunking it down into the smallest possible units, solving them, and adding up the results together. Read more about it here. ...

Going through Chapter 2 of CLRS, I was introduced to the concept of divide and conquer, which is a very interesting algorithm technique, and a popular example of the divide and conquer algorithm is merge sort. Merge sort has an Θ(nlgn) run time, which is very good for large inputs. When the input is sufficiently small enough, the algorithm has a worse run time compared to a sorting algorithm that completes in Θ(n^2) time. One of the exercises is to create an optimized version of the merge sort that runs the original merge sort algorithm for sufficiently larger inputs where it shines and to run insertion sort [ Θ(n^2) ] when the input size is sufficiently small enough. I have a solution for it on my Clio website, this post walks through the process for the solution. ...