Adding the time for terminal sublist col-lection and output givesTime < O(N(2 + log1b (N + 1))).If the sorted sublist is left in the memory, that is, not output,the constant two in the time estimate can be replaced by a one.When the list is output, the time approaches this time estimateas N approaches zero.The next section presents an implementation of a BT sorterwhich satisfies assumptions 1) and 2).IV. IMPLEMENTATION OF THE BT SORTERConceptually, a balanced tree sorter consists of a base bcomparator and a set of buckets. The base b comparator inputsan item, compares the item to all (b - 1) node values simul-taneously, determines the "nearest" node value, and assignsthe item to sublist associated with the node value. There is onebucket for each sublist and, to avoid assigning a separatememory to each sublist, each sublist is stored as a linked listand only a pointer to the sublist is stored in a bucket.The comparison between input and node values is executedby (b - 1) comparators, numbered 1, 2,.. , (b - 1), workingin parallel. The logical design of the comparators is straight-forward (see, for example, [6]). When an item is compared toall the node values,, it is assigned to the node whose value isnearest and less than the item value; that is, every item in aN+ (b -1)(bk -1) <bk+ I sublist is greater than or equal to the associted node value. Foritems which are less than all the node values, there is a specialbucket, Bucket (0). Since the buckets have to be referencedtwice for each item, the set of buckets is a separate fastmemory.At some point during a pass, the node values have to besorted. To avoid the time delay of a separate sort, we use thebase b comparator hardware itself to sort the node values asthey are loaded into the comparators. To do this, we compareeach incoming node value to the node values already enteredand alter the bucket values so that the node values form alinked list with the links stored in the buckets. This is essentiallyan insert in place sort using the base b comparator hardwareand a linked sorted list.An algorithm for a base b comparator isInitialize: I'= 0, Bucket (0)Set all node values equal infinityRepeat until list is emptyInput ItemIncrement ILet B = Location of "nearest" node valueMem (I) = ItemLink (I) = bucket (B)If I < b, then Comparator (I) = ItemBucket (I) = Bucket (B)Link (B) = IEnd ifBucket (B) = IEnd repeatwhere Mem and Link are the memories used to store the itemsand the links. The algorithm clearly satisfies assumption 1)and the total execution time is 0(N).At the end of a pass, this algorithm has already stored thenode values and their links in memory so no additional storagetime is necessary. The algorithm also leaves a link value whichis less than b to mark the end of every sublist except the last(the last item in the last sublist has a link value equal to @).The inpidual buckets each contain a pointer to the corre-sponding sublist with Bucket (0) containing a pointer to thefirst sublist. The sublists can therefore be processed duringlater passes using standard linked list techniques to access theitems.Assuming sufficient bucket memory is available, assigninga new set of buckets suffices to prepare the base b comparatorfor another pass using the same algorithm. Each sublist istreated as a separate list and the process repeated. The sublistscan be processed in breadth first order or depth first order.Breadth first, however, requires large amounts of bucketmemory. Processing the sublists in depth first order only re-quires 0(0ogb N) sets of bucket locations. Since the base bcomparator automatically sorts any sublist with length lessthan b, the left-to-right depth first order allows the output ofthe items in order each time a terminal sublist is processed.One advantage of the BT sorter'is that on later passes, noadvanced information about the size of a sublist is necessary.If the sublist is a terminal sublist, the sorted sublist is availableas soon as the items have been entered into the sorter. If thesublist is not a terminal sublist, then processing continues inthe balanced tree mode as soon as the node values have beenentered and sorted.To verify that assumption 2) is satisfied, we note that thetime to input and sort a terminal sublist is 0(n) and the timeto collect and output the sublist is also 0(n), so the total timeto sort and output a terminal sublist is 0(2n).V. PARALLEL BT SORTERSThe BT sorter generalizes cleanly to multiple BT sortersworking in parallel. Theoretically, if one has S-BT sortersworking in parallel, each sorting a separate subtree, the sorttime should be pided by S. Assuming that each subtree isstored in a separate memory so that no memory conflicts occur,it is clear that'sort times approaching 0((N/S) logb N) arepossible. The problem is to store the subtrees in separatememories and to avoid conflicts during the first pass.Conflicts arise during the first pass only if more than onesorter is trying to store items simultaneously in the samememory. Assume for example that there are S memories, onefor each sorter, and that the items associated with node i arestored in memory i(mod S); this assures that during laterpasses each sorter can work on a different set of 'subtreeswithout conflicts between sorters. 分拣机英文文献及中文翻译(3):http://www.youerw.com/fanyi/lunwen_30880.html