Hybrid Merge/Insertion sort algorithm
Optimization notes.

Allocate the temporary array once, and pass it down to the recursive invocations.

 Do not fall back to the insertion sort immediately. Postpone it until all the recursions complete, and insertion sort the entire array once.
It feels scary to insertion sort the entire array. Wouldn't it degrade performance to \$O(n^2)\$? The answer is no. The array is already &quot;almost sorted&quot;: every element is at most OPTIMIZED away from its final destination. Therefore, an inner loop does at most OPTIMIZED iterations per element, and the overall complexity is \$O(n * \texttt{OPTIMIZED})\$. This observation also hints that OPTIMIZED should be in a ballpark of \$\log n\$.
Edit: I don't know what I was thinking. The above is totally wrong (it is valid for quicksort, but not here), except the observation that OPTIMIZED should be in a ballpark of \$\log n\$.

A little-known trick allows to cut the number of comparisons in the insertion sort in half. Instead of
  while (j &gt;= left &amp;&amp; arr[j] &gt; key)

consider first comparing key to arr[left]:
  if (key &lt; arr[left]) {
      // The key shall land at the left. No need to compare values anymore
      for (j = i; j &gt; 0; j--) {
          arr[j] = arr[j-1];
      }
  } else {
      // arr[left] is a natural sentinel. No need to compare indices anymore
      for (j = i; arr[j] &gt; key; j--) {
          arr[j] = arr[j-1];
      }
  }

Now if you opt for a postponed insertion sort, it could be optimized even more: find the min among first OPTIMIZED elements and swap it with arr[0]. Now there is no need to test for key &lt; arr[left] - it is guaranteed to fail. Go straight into the unguarded loop.