Parallel mergesort, Multiprocessor algorithm, Performance analysis, Communication time, Decomposition time
The paper describes a performance model of a fine-grained, parallel mergesort which sorts N elements in 0(N) time using 0(logN) processors. The model predicts both the communication time involved in merging the elements and the decomposition time required to activate and terminate the binary tree of processes. The parallel algorithm is written in Joyce and runs on an Encore Multimax.
Hansen, Per Brinch, "Analysis of a Parallel Mergesort" (1989). Electrical Engineering and Computer Science Technical Reports. 55.