Divide and Conquer Algorithms
This article is written as a response to a technical interview question I wrote: Why are divide and conquer algorithms more efficient than other algorithms? Is there a time you should not use divide and conquer algorithms?
Divide and Conquer algorithms are more efficient because of the number of comparisons made. In a sorting example, selection sort has to review every single element n² times because of the way it is implemented; no amount of optimization of the algorithm will fix that its best-case runtime is (n²). Meanwhile, with a divide and conquer algorithm like merge sort, it will run in (n lg n) time no matter what. Because of the way merge sort, and other divide and conquer methods are implemented, it cannot end up worse than (n lg n) runtime. This is because merge sort splits each element into smaller and smaller arrays, or divides them, deals with the smaller arrays, normally down to 1 element, however some forms of merge sort can hand off to other sorting methods, in the conquer step of the process, then merges them back together, referred to as combining. During the combining process, merge sort gains back time because since the two sub arrays are already sorted, once one array runs out of elements, the rest of the elements in the other array are simply inserted at the end of the combined array. For a visual example, here is a step-by-step guide of merge sort versus selection sort, with each comparison that is being made for the data set [4, 9, 3, 1, 2].
As can be seen, merge sort ends quicker, even in a 5-element array. While this isn’t consistent for all arrays of this size, this increase only grows more drastic over time.
Applied to searching, the results are far more dramatic. Divide and conquer algorithms in searching require more setup in the fact they need to be sorted, but a binary search can find a value in (lg n) time, yet a simple loop search requires a (n) time. This is because binary search cuts the amount it is searching in half every single step, whereas a looping search requires viewing every single element no matter what. Overall, it becomes far more time effective if you are doing multiple searches to have the algorithms sorted.
As a combination of both searching and sorting, especially if you have to repeatedly access the values, it becomes far more valuable to have them sorted than to not. Divide and conquer algorithms do require more space, but overall, the space cost is more often than not worth it to complete the sorting and searching in a more efficient time.
Further Reading
Here are a couple of articles online that provide more information, as well as illustrate clearly the differences in using the different algorithms.
https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/
