Sorting Using Divide and Conquer

We shall now explore how to implement the divide-and-conquer approach when it comes to solving another standard problem – sorting. The importance of having an efficient sorting algorithm cannot be overstated. In the early days of computing in the 1960s, computer manufacturers estimated that 25% of all CPU cycles in their machines were spent sorting elements of arrays. Although the computing landscape has changed significantly over the years, sorting is still widely studied today and remains a fundamental operation in several applications. For instance, it is the key idea behind indexes in databases, which then allow quick access to the stored data using a logarithmic time search, which is similar to binary search.

The general requirements for an implementation of a sorting algorithm are as follows:

• The implementation should be able to work with any datatype. It should be able to sort integers, floating-point decimals, and even C++ structures or...