Today, we live in an era with great technological advantages, abundant resources and an infinity of data. We can learn about anything, from anywhere, at any time, at a reasonable cost. The devices we use every day are getting more powerful and cheaper day after day, which makes our problems easier and faster to solve.
One of the most important and most-used operations in computer science, even today, is sorting. Sorting applies simple principles and complex algorithms to give the best result. Each of these algorithms differs in structure and execution speed. Do these speeds depend solely on the complexity of the algorithm, or also on the computing power of the devices we use?
To answer this popular question, I started analysing tests and results of the execution time of the most-used, well-known sorting algorithms compared across computers with different processing power.
The execution time of an algorithm directly relates to the size of the input data and the complexity and efficiency of the algorithm itself. If we input more or bigger data, sorting algorithms take more time to produce results. If the algorithm is more complex, results calculate more slowly. However, if the algorithm is more efficiently constructed, we get results faster.
Execution time is directly proportional to power consumption — after running a few tests, it turned out that some algorithms run faster than others. Algorithms with low CPU time tend to have lower power consumption, resulting in slower execution time. This means a linearly constructed algorithm will calculate results faster on a computer with less processing power than on a state-of-the-art machine.
The reason is how the algorithm is constructed. A linear-base algorithm uses one thread of the CPU and calculates linearly — operations happen in order, from left to right, one at a time. Consequently, we don’t need greater processing power, because the algorithm won’t use it, and it won’t affect execution time.
The processors we use today are multi-core and multi-threaded, with great clock speeds and low power consumption. To use them for speeding up sorting execution time, we should first reconstruct the algorithm from linear to parallel. This results in the parallel algorithm using all the threads of the multi-core processor instead of one. We can accelerate calculations even further using GPU CUDA processing, but that’s a discussion for another day.
Using parallel-constructed algorithms with today’s CPUs and their huge processing power, the execution time of sort algorithms is not much affected by the size or quantity of input data.
In conclusion, to speed up the execution time of algorithms, we first need to reconstruct them as parallel and increase their efficiency. This way, our multi-core, multi-threaded, high-processing-power CPUs can properly accelerate the calculations of sorting results — working in parallel instead of linearly, calculating more operations at a time. However, if we use linear algorithms, processing power makes no difference, since operations happen in order, using only one thread of the processor.