Why is merge sort considered to be best

Question

Why not insertion sort with binary insert is considered to be best ?

Merge sort : T(n) = n + 2*T(n/2) = O(n*log(n))  
But insertion sort with binary insert : T(n) = log(n-1) + T(n-1) = O(log(n!))  
and n^n > n! ; so n*log(n) > log(n!)

for bigger n, it would really help to improve performance.

Or am I missing something ?

Forgive me if I am asking too trivial question, I am new to programming and I just want to get the facts right.

Answer 1

I think your estimation of insertion sort's complexity is wrong. You didn't describe the details of how you got the result, but it seems you forgot about the time needed to insert - I mean the time you need to move some part of the sorted array to make place for the element you are inserting.

After you sorted n-1 elements, you need O(log(n)) time to find the place for n-th element and O(n) (pessimistically) time to move part of the sorted array and make place for the n-th element. So the total complexity is

O(1 + ... + n + log 1 + ... + log n) = O(n^2 + n log n) = O(n^2).

You don't improve your algorithm by binary search, because you have to shift part of array (of linear size in terms of n) anyway.

Answer 2

The insertion sort with binary insert has a running time of O(n^2) on an average. Try exploring the wiki page here. Also, check out this SO post.