This article compares several network sorting algorithms, among them the quicksort variant by L. Wegner which is found to out-perform all others.
A model for distributed sorting on a local area network (LAN) is built, which contrary to the conventional model, takes into account both local processing time and communication time. This model is intended to provide a framework within which the performance of various distributed sorting algorithms can be realistically analyzed. Five distributed sorting algorithms are analyzed and implemented on Ethernet-connected Sun workstations. The empirical results by and large agree with the predictions derivable from the model. They show that local processing, particularly sorting of local subfiles, dominates the whole process, as far as response time is concerned. All algorithms examined have a similar asymptotic behavior for large files. For medium-sized files, the degree of communication parallelism has a great impact on algorithm performance. For example, algorithm of the divide-and-conquer type (e.g. Distributed Quicksort) perform well because of their inherent high degree of parallelism. The fact that the distributed sorting on LAN's can be very efficient and can achieve a significant speedup over the sorting in a single machine demonstrates the feasibility of parallel processing involving powerful workstations connected together by a LAN.