The use of binary search trees in external distribution sorting

摘要

A new method of external distribution sorting called tree partitioning is suggested. It involves the use of a binary tree to split an incoming file into successively smaller partitions until these are small enough to be sorted internally. The tree is generated from a sample of data of the same type as those to be sorted using that tree. The method is therefore suitable in cases where some regularity in the data is to be expected, as is the case, for example, with words from a textual or bibliographic database. The number of disc accesses during a tree partitioning sort were calculated in a simulation using files of up to 900,000 text words extracted from British National Bibliography catalogue files. These were compared with the actual numbers of disc accesses used by a standard sort-merge utility. Although the differences were in general not large, the comparison was favourable to tree partitioning in the majority of cases.