I went over the sorting algorithm with two methods and thought that if we reduce the merge, we can get the best win in terms of time.
For example, in two-dimensional merging, we have the following recurrence:
T (n) = 2T (n / 2) + O (n)
and this has the time complexity of N.log-base2 (N)
if I divide the problem by 4 and combine 4 submatrices, I will get
T (n) = 4T (n / 4) + O (n)
and this should have the time complexity of N.log-base4 (N)
Since the number of merge passes has decreased, should this be something to consider when implementing a merge sort?
for example, with an array of 64 elements, the first approach will have 6 passes and using the second approach will have 3 passes.
Edit:
, 2T (n/2) N 4T (n/4), 3 * N ? , , ?