Merge with Co-rank Divide the output into regular intervals Compute the co-ranks for each output interval endpoint i2=5 j1=1 1g=2 11=5 1。=1 j2=4 A: 8 9 10 B: 7 1010 12 C: 8 9 10 10 10 12 k。=3 k1=6 k2=9
Merge with Co-rank • Divide the output into regular intervals • Compute the co-ranks for each output interval endpoint
Merge with Co-rank Thread 0:C[O k0]merge(A[O:i0],B[O j0]) Thread 1:C[k0 k1]merge(A[i0 il],B[jo j1]) Thread 2:C[kl:k2]merge(A[il i2],B[jl j2]) 12=5 =1 =2 11=5 j。=1 j2=4 A: 8 9 10 B: 10 10 12 C: 8 9 10 10 10 12 k。=3 k1=6 k2=9
Merge with Co-rank • Thread 0: C[0 : k0] ⇐ merge(A[0 : i0], B[0 : j0]) • Thread 1: C[k0 : k1] ⇐ merge(A[i0 : i1], B[j0 : j1]) • Thread 2: C[k1 : k2] ⇐ merge(A[i1 : i2], B[j1 : j2])