why mergeSort faster than insertion in java

Question

I wrote a code in java using int insertion and int mergeSort. also String insertion and String mergeSort. my question is why mergeSort always faster?

Answer 1

Because InsertionSort has time complexity O(n^2) while MergeSort has time complexity O(nlogn).

Have a look here for a simple comparison of all the sorting algorithms. You can read more here, here and here.

As a simple example, if you have 100 elements to sort, InsertionSort will do 100^2 = 10 000 operations to sort it, while MergeSort will do it with 100*log(100) = 100*2 = 200 operations, making it 50 times faster.

This becomes very important for large sets of data. When sorting an array of 1 000 000 objects, InsertionSort will perform 1 000 000 000 000 operations while MergeSort will only perform 6 000 000, making it 166 666 times faster.

In the above case, assuming you are using a computer that can do 1 billion operations per second, it would take InsertionSort 17 minutes to sort them, while MergeSort will do it in 6 milliseconds.

Do note that the above figures and time complexities apply on an average case.