Merge Sort

Tư tưởng :

Có hai dãy đã xếp trộn thành một dãy được xếp

Dãy có một phần tử : dãy đã được xếp

+ Tiến hành chia đôi dãy ban đầu và tiếp tục chia đôi 2 dãy con nhận được cho đến khi nhận được dãy con có độ dài =1

à đã được xếp

+ Trộn từng cặp dãy con đã được xếp thành một dãy con được xếp lớn hơn ,tiếp tục thực hiện cho đến khi nhận được 1 à dãy ban đầu đã được xếp .

Thuật toán trộn 2 dãy con kế tiếp nhau đã được xếp

Chia để trị : t=(l+r)/2

- Trộn hai dãy con đã xếp : C=A&B

Đặt con trỏ i vào đầu dãy A

Đặt con trỏ j vào đầu dãy B

+ phần tử nhỏ hơn ở đầu hai dãy để đưa vào dãy mới (phần tử đầu ở dãy đã lấy ra dịch thêm 1 phần tử )

+ Lặp lại bước trên đến khi 1 trong 2 dãy đã hết

+ Đưa nốt phần còn lại của dãy chưa hết vào dãy mới .

Thủ tục :

void Merge(int X[20],int a,int m,int b)

{

int C[20];

int i=a,j=m+1,k=a,t;

while(i

{

if(X[i]

{

C[k]=X[i];

i=i+1;

}

else

{

C[k]=X[j];

j=j+1;

}

k=k+1;

if(i>m)

for(t=j;t

{

C[k]=X[t];

k++;

}

else

for(t=i;t

{

C[k]=X[t];

k++;

}

for(int h=a;h

X[h]=C[h];

}

void MergeSort(int X[20],int l,int r)

{

if(l

{

int t;

t=(l+r)/2;

MergeSort(X,l,t);

MergeSort(X,t+1,r);

Merge(X,l,t,r);

}

}

Độ phức tạp của giải thuật :

- Tổng số lần so sánh

Có log2n bước trộn

à C(n) có bậc O(nlog2n)

- Tổng số lần đổi chỗ :

Có log2n bước trộn

à M(n) có bậc O(nlog2n)

Vậy thời gian thực hiện giải thuật Merge Sort có độ

phức tạp là O(nlog2n)