对数划分技术 划分方法 n个元素A[1.n分成A[(-1)logn+1..ilogn,i=1~n/1ogn *示例：PRAM-CREW.上的对数划分并行归并排序 (1)归并过程：设有序组A[1.n和B[1m B B= ···bogm b2o啊 b()logm A= a···a0 a0)+ ···a2) ai)+1 a(4) 4 A A j间=rank(boem:A)为boem在A中的位序，即A中小于等于boem的元素个数 (2)例：A=(4,6,7,10,12,15,18,20),B=(3,9,16,21)n=8,m=4 =>logm=1og4=2 =>j[1]=rank(bIogm:A)=rank(b2:A)=rank(9:A)=3,j[2]=.=8 Bo:3,9B:16,21 A:4,6,7A:10,12,15,18,20 A和B归并化为(Ao,B)和(A1,B)的归并 2011/10/25 16对数划分技术  划分方法 n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn  示例：PRAM-CREW上的对数划分并行归并排序 (1)归并过程: 设有序组A[1..n]和B[1..m] j[i]=rank(bilogm:A)为bilogm在A中的位序，即A中小于等于bilogm的元素个数 (2)例：A=(4,6,7,10,12,15,18,20), B=(3,9,16,21) n=8, m=4 =>logm=log4=2 => j[1]=rank(blogm:A)=rank(b 2:A)=rank(9:A)=3, j[2]=…=8 B 0: 3, 9 B1: 16, 21 A 0: 4, 6, 7 A1: 10, 12, 15, 18, 20 A和B归并化为(A 0, B 0)和(A1, B1)的归并 1 log = 1 1 = 1 i ... ... ... ... log +1 ... ... (1) (1)+1 (2) ... ... 2log log +1 ( +1)log ( )+1 ( +1) ... ... 0 0 16 2011/10/25