Combining merge sort and insertion sort
Basic Idea

For small values of n insertion sort runs faster than merge sort . Hence insertion sort can be used to Optimize merge sort

Basic idea is apply insertion sort on sublists obtained in merge sort and merge the sorted (using insertion sort) lists


Coming to Question
Base Condition
If each word is 4-byte long, then a 128-byte cache contains 32 words. Therefore, if the problem size is 32 or less, the instance will be immediately solved by Insertion Sort, otherwise it will be split in two sub-problems with the same size, which will then have to be merged
Time Complexity

Total Complexity = Complexity Insertion Sort + Complexity of Merge Sort

We have $n$ elements . We are dividing it to $\frac{n}{x}$ sublist each contain x elements each

Complexity Of Merge Sort

Total work done by merge sort in copying $n$ elements from each level to upper level is $O(n)$
Number of levels = number of sublists or small problem = $O(\log \frac{n}{x})$
Complexity of Merge sort : $O( n \log \frac{n}{x} )$

Complexity Of Insertion Sort

We are sorting $ \frac{n}{x} $ lists each of $x$ elements using insertion sort so complexity contributed by insertion sort is $\frac{n}{x} $ INSERTION ${x}$


Total Complexity =  $\Theta ( \frac{n}{x}  \ \text{INSERTION} \ (x)  +  n \log \frac{n}{x} )$

Best Case

is when Insertion sort perform in best case with $O(n)$ ie $\text{INSERTION} \ (x) = x$
Best Case Complexity=Total Complexity =  $\Theta ( n  +  n \log \frac{n}{x} )$

Worst Case

is when Insertion sort perform in best case with $O(n^{2})$ ie $\text{INSERTION} \ (x) = x^{2}$
Best Case Complexity=Total Complexity =  $\Theta ( nx  +  n \log \frac{n}{x} )$

More Information : Gate Overflow - Sorting Algorithm