title: Optimizing merge sort for cache misses
body: <p>Consider an unsorted array of N elements wherein each element is byte sized.   Let  the  size  of  the  cache  be  1  KB  with  a  cache  line  size  of  64.Further assume that the cache is organized in a fully associative manner.Compute  the  number  of  cache  misses  when  a  merge  sort  algorithm  is applied on the array.  While doing the analysis, you may want to consider different cases comparing the array size N with the cache size. Do you have any suggestions on modifying the merge sort algorithm so as to reduce the cache misses.
  Assume the merge sort algorithm uses 1 temporary array to store the elements of the 2 arrays being merged.</p>