What you implemented is Top-down mergesort, which means to split the array into two parts, sort each, and merge them together. This is done recursively. The problem of it is, assuming the array has 12 elements, then it would split the array into 2 6-element arrays, that would take no advantage of the fact that every 4 elements are already sorted.
You should instead use Bottom-up mergesort, that is, split the array into subarrays, each of the subarrays have 4 elements. Since each of them are already sorted, merge every two subarrays into 8-element subarrays, and then merge every two 8-element subarrays into 16-element subarrays, and so on. The code of sorting N-element array is like this:
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, min(lo+sz+sz-1, N-1));
Since you already know that every 4 elements are sorted, you can start with sz
being 4
, which takes full advantage of the knowledge.