Algorithm Efficiency : Merge sort vs Insertion sort

Algorithm Efficiency : Merge sort vs Insertion sort

Importance of Algorithm Efficiency :

Let us learn how an algorithm efficiency matters a lot ? We will analyse this by taking some interesting experiment as an example. Before that let us know what are the efficiencies of both the algorithm

Insertion sort :

 The average and worst case efficiency of merge sort is (C1) O(n2)

Merge Sort :

 The average and worst case efficiency of merge sort is (C2) O(nlog(n)) 

But let us analyse the efficiency with an experiment :

Experiment :

Let us take a faster computer , Computer A running insertion sort and a slower computer running merge sort.

They each must sort an array of one million numbers. Considering the following factors

  • Computer A executes one billion instructions per second
  • Computer B executes ten million instructions per second
  • Computer A is 100 times faster than Computer B in raw computing power
  • To make the difference even more dramatic , suppose that the world’s craftiest programmer writes insertion sort in machine level language for Computer A and resulting code requires 2n2 instructions to sort n numbers ( 2 is constant c1)
  • Merge sort  will be developed by an average programmer using high-level language with an efficient compiler with a resulting code 50nlog(n) instructions ( 50 is constant c2)

With the above assumptions , to sort one million numbers

Time taken by Insertion Sort in Computer A ( Faster computer ) :
( 2 X (106)2 Instructions ) / 109 instructions/second = 2000 seconds,

Time taken by Merge Sort in Computer B ( Slower Computer ) :
(50 X 106 lg(106) Instructions) / 107 instructions/second = 100 seconds,
This experiment shows even with slower computer (100 times slower) the best algorithm gives best result compared to faster computer running less efficient algorithm.

Computer B runs 20 times faster than Computer A, even though Computer A is 100 times faster than Computer B.

This proves that even though the underlying hardware is low end, an efficient algorithm performs much better, one very good example for this is Android vs iOS 🙂

Even though android smart phones are very high end , very good RAM and processor, they perform less compared to iPhone which has less RAM and less speed processor
Reference : Introduction to algorithms by Thomas H. Cormen