Skip to main content

Why Merge Sort is better than Insertion Sort

Why Merge Sort is better than Insertion Sort

Insertion sort is better for small number of inputs ony but while incrementing the number of inputs to 1000 or millions or billions , Merge sort performs better than Insertion Sort .

To decide the better algorithm , we need to look at the time complexities of both sorting algorthms before . While executing an algorithm if it uses n inputs then the time complexity for Insertion sort is pn*n and for Merge Sort is q*n*ln n . Here p and q are constants and generally p < q .

Time complexity does not depend on the constants like p and q .

To understand it deeply , We take two computers A and B with the following features -

  • A is with good Architecture and  much faster than computer B .
  • B is with poor achitecture and slower than computer A .
  • We are executing Insertion Sort on the computer A and Merge sort on Computer B .
  • Both of these algo differs with respect to n and ln n terms in the complexities . 
  • If we test both of them for n = 100 inputs then the Insertion sort takes n=100 but Merge sort takes ln n = ln 100 = almost 5 .
  • If number of inputs is 1000 then merge sort growthing term ln n gives only ln(1000) = almost 10 .

Thus for large number of inputs Merge sort  becomes fast and performs better because it's growth rate is in terms of ln n and growth rate of insertion sort is in terms of n for No matter the computer speed . .