Merge Sortを4で割ったもの - 擬似コードの時間複雑度

Question

Merge Sort（4で割ったもの）の擬似コードを書く必要があります。時間の複雑さが分かります（Nlog（n ）明らかに）。

これは私が書いたものである：

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 -

マージ関数は2つの配列をマージし、ソートされた要素のための新しい配列を作成XにB、C、D、Rアレイを分割。 私は混乱してしまいどこ

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

時間の複雑さがある（マージ機能は、わずか2ウェイマージソートのようです）。

明らかに、T（N）= 4T（N/4）（4つの問題に分割）

しかし、私は、分割後に何が起こるかわかりません。

私の最高の推測では、次のようになります。T（N）= 4T（N/4）+ O（n）の

ガイドラインをいただければ幸いです

...

Answer 1

結局、最終的な答え：

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)