Premium
A parallel version of cook and Kim's algorithm for presorted lists
Author(s) -
McGlinn Robert J.
Publication year - 1989
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380191002
Subject(s) - quicksort , computer science , sorting algorithm , parallel computing , multiprocessing , sorting , parallel algorithm , merge sort , extension (predicate logic) , algorithm , sort , programming language , information retrieval
The Cook and Kim algorithm is a well known method for sorting presorted lists. This paper presents observations based on an implementation of the algorithm on a single processor. An extension of the algorithm to a tightly coupled multiprocessor will also be presented. The performance of the parallel version of the algorithm on presorted lists will be compared to that of a heavily used parallel sort algorithm for tightly coupled multiprocessors, Parallel Quicksort.