Combining merge sort and insertion sort

A cache-aware sorting algorithm sorts an array of size $ 2^{k} $ with each key of size 4 bytes. The size of the cache memory is 128 bytes and algorithm is the combinations of merge sort and insertion sort to exploit the locality of reference for the cache memory (i.e. will use insertion sort when problem size equals cache memory).


What are the best case and worst case running time of the algorithm?

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

StackExchange Computer Science Q#68179, answer score: 4