reset password
Author Message
venny
Posts: 61
Posted 14:00 Apr 09, 2015 |

 Can someone explain to me why insertion sort O(n^2) is more efficient than merge sort O(n log n) when the number of inputs is smaller ? According to my book (which is not explaining how), insertion sort is more efficient..... though if I was to plug n = 2 then merge sort would have a smaller O right? 

Last edited by venny at 14:05 Apr 09, 2015.
clarenceann
Posts: 16
Posted 14:23 Apr 09, 2015 |
I think the book says that insertion sort is good when dealing with smaller amounts. But when it starts to get bigger that's when merge sort outperforms. I think that's what I remember reading
sya
Posts: 10
Posted 17:29 Apr 20, 2015 |

Hey Venny,

I just read up on it a bit, and from what I understood, it goes with Clarences' comment, as the worst case time for merge is O(nlogn) and for insertion its O(n^2), but the best case for insertion is O(n), where for merge its still O(nlogn).

The book is just really bad at describing things in comprehensive terms imo.

vsluong4
Posts: 87
Posted 17:31 Sep 24, 2015 |

For the purposes of this class, we ignore constants. 

 

Including constants, insertion sort has a complexity of about 8n2, while merge sort is about 64nln(n).  Some simple math reveals that there is a point where insertion sort is faster, because the constant is smaller.   Some sorts take advantage of the fact that insertion sort is fast on a small scale, to get faster overall.

 

Another way to think about it is that if you have twice as many things to sort, insertion sort isn't twice as slow, it's four times as slow (n2).  But, if you have half as many elements, insertion sort isn't just twice as fast, it is four times as fast.