方根划分技术 划分方法 n个元素A[1.n]分成A[i-1)n(1/2)+1in^(1/2,i=1~n^(1/2) 米 示例：SMD-CREW模型上的k=pa]Valiant)归并(1975年发表) /有序组A[1p小、B1ql,(假设p<=q),处理器数k=LVpg begin ()方根划分：A,B分别按Vp和Vg份成若干段(i=1~Vpj=1~」； 2)段间比较：A划分元与B划分元比较（至多DLg对）， 确定A划分元应插入B中的区段； (③)段内比较：A划分元与B相应段内元素进行比较，并插入适当的位置； (4)递归归并：B按插入的A划分元重新分段，与A相应段(A除去原划分元) 构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束；各组仍按k=VP9分配处理器； end. 2011/10/25 11方根划分技术  划分方法 n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)  示例：SIMD-CREW模型上的 Valiant归并(1975年发表) //有序组A[1..p]、B[1..q], (假设p<=q), 处理器数 begin (1)方根划分: A,B分别按 ； (2)段间比较: A划分元与B划分元比较(至多 对)， 确定A划分元应插入B中的区段； (3)段内比较: A划分元与B相应段内元素进行比较，并插入适当的位置； (4)递归归并: B按插入的A划分元重新分段，与A相应段(A除去原划分元) 构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束; 各组仍按 分配处理器； end. i p  和 j  q 分成若干段（i 1 ~  p 、j 1 ~  q  ） 11 2011/10/25 k   pq  k   pq   p  q  k   pq 