【資料結構】二路合併排序(2-way merge sort)/(collating sort)

二路合併排序(2-way merge sort)/(collating sort)

重點為二：

1.      將n個，長度1的keys，合併程n/2個，長度2的keys…直到1個，長度n的key

2.      合併時順便做排序(每次均為二路相互比較成一組)

程式碼運作如下：

========================================================================

void merge (int a[], int m, int p,int n,int b[])

{
int i,j,k;
i=m;
j=p+1;
k=m;
while (i<=p && j<=n)
if(a[i]<=a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
while(i<=p)
b[k++]=a[i++];
while(j<=n)
b[k++]=a[j++];
}
int * MergeSort(int *x, int *y, int n)
{
int len, *t;
for(len=1; len<n; len*=2)
{
for(int s=1 s+len<=n; s+=2*len)
if(s+2*len-1>n)
merge(x,s,s+len-1,n,y);
else
merge(x,s,s+len-1,s+len*2-1,y);
t=x;
x=y;
y=t;
}
return x;
}
========================================================================

題目：

外部排序（external sorting）最常使用的是2-way合併排序法（merge sorting）。假設檔案裡面包含18000筆資料，而記憶體最多只能容許3000筆資料。假設每次I/O block大小為1000筆資料，則需讀多少次I/O block才能完成排序？

解法：

A.     在分段排序階段：

18000/3000=6段資料，而每段3000/1000=3次I/O block，共需6*3=18次I/O block

B.     在分段合併階段：

a.       回合一：

 

b.      回合二：

c.       回合三：

得到解答：

共需18+18+12+18=66次I/O block