Analysis of the performance of the parallel quicksort method

DOI10.1007/BF01934992MaRDI QIDQ1070824zbMATH OpenOpenAlexFDO

Authors Nadia Y. Yousif, D. J. Evans

Publication date 1985

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934992

zbMATH Keywords

linear insertionparallel computationpartitioning processperformance on a parallel MIMD computerquicksort algorithmspeed up rate

Mathematics Subject Classification ID

Theory of operating systems (68N25) Searching and sorting (68P10) Algorithms in computer science (68W99)

Review text

This paper deals with the quicksort algorithm and its performance on a parallel MIMD computer. Using the analysis of the quicksort algorithm by Knuth and Sedgewick the authors derive approximations for the speed up ratio for a varying number of processors and a varying size of the small subfiles which are finally sorted by some insertion sort. The theoretical estimates are rather rough compared to the results of the experiments and the theoretically derived speed up rate is considerably higher than the experimentally achieved result. However the tendency is the same and the results presented can constitute a starting point for more appropriate estimates.

Recommendations

• scientific article; zbMATH DE number 784426
• An experimental analysis of parallel sorting algorithms
• Analysis and benchmarking of two parallel sorting algorithms: Hyperquicksort and quickmerge
• An efficient parallel sorting algorithm for shared memory multiprocessors
• A parallel sorting-merging algorithm for tightly coupled multiprocessors

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Implementing Quicksort programs
• Quicksort
• The parallel quicksort algorithm part 2—simulation
• The parallel quicksort algorithm part i–run time analysis

Cited in

(5)

• A parallel partition for enhanced parallel QuickSort
• Exploiting partial order with Quicksort
• scientific article; zbMATH DE number 784426 (Why is no real title available?)
• Analysis of Branch Misses in Quicksort
• A fully vectorized quicksort

Describes a project that uses

Uses Software

• Find
• Quicksort

This page was built for publication: Analysis of the performance of the parallel quicksort method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1070824)