Question

Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into two parts like Merge sort, 4-way Merge sort splits the array into four parts. 4-way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths.
a) Give pseudocode for 4-way Merge sort.
b) State a recurrence for the number of comparisons executed by 4-way Merge sort and solve to determine the asymptotic running time.

Answer 1

a)

Algorithm:

Four_Way_Merge_Sort (A,left,right):

if(left<right)

{

p=left

r=left+(right-left)/2;

q=p+(r-p)/2

s=r+(right-r)/2

Four_Way_Merge_Sort(A,p,q)

Four_Way_Merge_Sort(a,q+1,r)

Four_Way_Merge_Sort(a,r+1,s)

Four_Way_Merge_Sort(a,s+1,right)

Four_Way_Merge(a,p,q,r,s,right)

}

Algorithm:

Four_Way_Merge(a,p,q,r,s,right)

{

sz1=q-p+1

sz2=r-q

sz3=s-r

sz4=n-s

p1[1,...,sz1]

p2[1,...sz2]

p3[1,...sz3]

p4[1,...sz4]

for (i = 0 to sz1)

{

p1[i]=a[p+i]

}

for (i = 0 to sz2)

{

p2[i]=a[q+1+i]

}

for (i = 0 to sz3)

{

p3[i]=a[r+1+i]

}

for (i = 0 to sz4)

{

p4[i]=a[s+1+i]

}

i = 0

j = 0

l=0

m=0

k = p

while (i<sz1 && j<sz2 && l<sz3 && m<sz4)

{

if (p1[i]<=p2[j]&&p1[i]<=p3[l]&&p1[i]<=p4[m])

{

a[k]=p1[i]

i++

}

else if (p2[j]<=p1[i]&&p2[j]<=p3[l]&&p2[j]<=p4[m])

{

a[k]=p2[j]

j++

}

else if (p3[l]<=p1[i]&&p3[l]<=p2[j]&&p3[l]<=p4[l])

{

a[k]=p3[l]

k++

}

else

{

a[k]=p4[m]

l++

}

k++

}

  

while(i<sz1)

{

a[k]=p1[i]

i++

k++

}

while(j<sz2)

{

a[k]=p2[j]

j++

k++

}

while(l<sz3)

{

a[k]=p3[l]

l++

k++

}

while(m<sz2)

{

a[k]=p4[m]

m++

k++

}

}

b)

At each recursive step we divide a problem of size n into four sub-problems each of size n/4, and merge takes O(n) time.

So the recurrence relation of our algorithm is:

T(n)=4T(n/4)+O(n)=O(n log n).