Merge Sort divided by 4 - Time complexity of the pseudo code

Question

I need to write a pseudo code for a Merge Sort (divided by 4), and figure out it's time complexity (And it must be in time complexity of Nlog(n) obviously).

This is what I wrote:

    Mergesort4(A){
    If   (n <= 1 ) return (A) 
    if (n=0) return(infinity) (Big number)

    k = (n/4)  m=(2n/4)  z=(3n/4)
    Return Merge4(Mergesort4(A[0..k-1]), Mergesort4(A[k..m-1]), 
                 Mergesort4(A[m..z-1]), Mergesort4(A[z..n-1), A[0..n-1])
    }

Merge4 - Divides B,C,D,R arrays into X.

Merge function merges 2 arrays, and creating a new array for the sorted elements. (the Merge function is just like in the 2-way Merge sort)

Merge4(B,C,D,R,X){
          Merge(B,C,E)
          Merge(D,R,T)
          Merge(E,T,X)
}

The Time complexity is where I get confused.

Obviously, T(n)=4T(n/4) (divides into 4 problems)

But I'm not sure what happens after the division.

My best guess would be: T(n)=4T(n/4) + O(n)

Guidelines would be appreciated...

Answer 1

Eventually, the final answer:

Mergesort4(A,p,r)
    If(q < r)
        q = floor( (p+r)/4 )
        Mergesort4(A, p, q)
        Mergesort4(A, q+1, 2q)
        Mergesort4(A, 2q+1, 3q)
        Mergesort4(A, 3q+1, r)
        Merge( A, p, q, q+1, 2q, 2q+1, 3q, 3q+1, r)


Merge( A, p, q, q+1, 2q, 2q+1, 3q, 3q+1, r )

    if(q != 0 && p != 0)
        Merge(A,p,q,2q)
    Merge(A,2q+1,3q,r)
    Merge(A,p,2q+1,r)