algorithm Multithreaded Algorithms merge-sort multithread
Example
A is an array and p and q indexes of the array such as you gonna sort the sub-array A[p..r]. B is a sub-array which will be populated by the sort.
A call to p-merge-sort(A,p,r,B,s) sorts elements from A[p..r] and put them in B[s..s+r-p].
p-merge-sort(A,p,r,B,s)
n = r-p+1
if n==1
B[s] = A[p]
else
T = new Array(n) //create a new array T of size n
q = floor((p+r)/2))
q_prime = q-p+1
spawn p-merge-sort(A,p,q,T,1)
p-merge-sort(A,q+1,r,T,q_prime+1)
sync
p-merge(T,1,q_prime,q_prime+1,n,B,s)
Here is the auxiliary function that performs the merge in parallel.
p-merge assumes that the two sub-arrays to merge are in the same array but doesn't assume they are adjacent in the array. That's why we need p1,r1,p2,r2.
p-merge(T,p1,r1,p2,r2,A,p3)
n1 = r1-p1+1
n2 = r2-p2+1
if n1<n2 //check if n1>=n2
permute p1 and p2
permute r1 and r2
permute n1 and n2
if n1==0 //both empty?
return
else
q1 = floor((p1+r1)/2)
q2 = dichotomic-search(T[q1],T,p2,r2)
q3 = p3 + (q1-p1) + (q2-p2)
A[q3] = T[q1]
spawn p-merge(T,p1,q1-1,p2,q2-1,A,p3)
p-merge(T,q1+1,r1,q2,r2,A,q3+1)
sync
And here is the auxiliary function dichotomic-search.
x is the key to look for in the sub-array T[p..r].
dichotomic-search(x,T,p,r)
inf = p
sup = max(p,r+1)
while inf<sup
half = floor((inf+sup)/2)
if x<=T[half]
sup = half
else
inf = half+1
return sup
