Name
Title | ||
|---|---|---|
A Simple, Fast Parallel Implementation of Quicksort and its Performance Evaluation on SUN Enterprise 10000 |
Abstract | ||
|---|---|---|
We have implemented sample sort and a parallel version of Quicksort on a cache-coherent shared address space multiprocessor: the SUN ENTERPRISE 10000. Our computational experiments show that parallel Quicksort outperforms sample sort. Sample sort has been long thought to be the best, general parallel sorting algorithms, especially for larger data sets. On 32 processors of the ENTERPRISE 10000 the speedup of parallel Quicksort is more than six units higher than the speedup of sample sort, resulting in execution times that were more than 50% faster than sample sort. On one processor parallel quicksort achieved 15% percent faster execution times than sample sorting. Moreover because of its low memory requirements, parallel Quicksort could sort data sets twice the size that sample sort could under the same system memory restrictions. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/EMPDP.2003.1183613 | ELEVENTH EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED AND NETWORK-BASED PROCESSING, PROCEEDINGS |
Keywords | Field | DocType |
additional key words and phrases: shared memory multiprocessors,parallel sorting,parallel quicksort,parallel algorithms,sorting,sorting algorithm,cache coherence | Merge sort,Computer science,American flag sort,Insertion sort,Parallel computing,Quicksort,Selection sort,Introsort,Bucket sort,Sorting algorithm,Distributed computing | Conference |
Citations | PageRank | References |
31 | 2.43 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philippas Tsigas | 1 | 1200 | 99.58 |
| Yi Zhang | 2 | 154 | 10.62 |