Optimizing Mergesort

Question

Merge-sort is a fairly common sorting algorithm, and I have written a working merge-sort algorithm. Then I want to optimize it. The first step was to convert it from a recursive to an iterative one, which I did. Then I couldn't discern what else can be optimized. After poring through lots of articles on internet, I got two mechanisms, using multi-merge sort and tiled merge-sort. However none of the documents provided any pseudo-code, or even cared to explain much on how to do it, and how does it offer the advantages its author says it does, like being cache-friendly and improved locality hit.

Can anyone elaborate on this matter, and if possible, provide some pseudo-code? Specifically, I want to know how to make it cache-friendly. I have absolutely no idea about what these things are, otherwise I would have tried it myself.

Answer 1

One common and relatively straightforward optimization you can make is to switch from mergesort to another algorithm like insertion sort when the subarray sizes get below a certain threshold. Although mergesort runs in time O(n log n), that talks about its long-term growth rate and doesn't say anything about how well the algorithm will perform on small inputs. Insertion sort, for example, runs pretty fast on small input sizes even though it's worse in the long run. Consequently, consider changing the base case of your mergesort so that if the array to sort is below a certain size threshold (say, 50-100), you use insertion sort rather than continuing onward in the recursion. From experience, this can markedly improve the performance of the algorithm.