Sorting Algorithms

Complexity of algorithms is an issue more important than the raw power of the available hardware.

Let’s take example the register of names of all people in US – roughly 300.000.000 persons.

To sort this list alphabetically with QuickSort we need about 1 second on a average computer(1 core), as the execution time for this algorithm is O (nlog n). Using a  slower algorithm (Selection Sort(complexity O(n2)) we need no less than 128 days -> 10.000.000 times slower . Using this slow algorithm, not even the biggest available  supercomputer(Currently 10.000.000 cores, top500.org) won’t be able to outperform  our normal computer using QuickSort -> so most of the times is better worth investing in good coders than expensive hardware.

Here for example we compare  3 sorting algorithms for different arrays size.

I included this nice comparison of different sorting algorithms  from K. Wayne’s, RS  class on algorithmics :

Leave a Reply

Your email address will not be published. Required fields are marked *