balanced_quicksort.h File Reference

Implementation of a dynamically load-balanced parallel quicksort. More...

#include <parallel/basic_iterator.h>
#include <bits/stl_algo.h>
#include <bits/stl_function.h>
#include <parallel/settings.h>
#include <parallel/partition.h>
#include <parallel/random_number.h>
#include <parallel/queue.h>

Go to the source code of this file.

Classes
struct	__gnu_parallel::_QSBThreadLocal< _RAIter >
	Information local to one thread in the parallel quicksort run. More...

Namespaces
	__gnu_parallel
	GNU parallel code for public use.

Functions
template<typename _RAIter , typename _Compare >
std::iterator_traits< _RAIter > ::difference_type	__gnu_parallel::__qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
	Balanced quicksort divide step. More...
template<typename _RAIter , typename _Compare >
void	__gnu_parallel::__qsb_conquer (_QSBThreadLocal< _RAIter > **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait)
	Quicksort conquer step. More...
template<typename _RAIter , typename _Compare >
void	__gnu_parallel::__qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)
	Quicksort step doing load-balanced local sort. More...
template<typename _RAIter , typename _Compare >
void	__gnu_parallel::__parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
	Top-level quicksort routine. More...

Detailed Description

Implementation of a dynamically load-balanced parallel quicksort.

It works in-place and needs only logarithmic extra memory. The algorithm is similar to the one proposed in

P. Tsigas and Y. Zhang. A simple, fast parallel implementation of quicksort and its performance evaluation on SUN enterprise 10000. In 11th Euromicro Conference on Parallel, Distributed and Network-Based Processing, page 372, 2003.

This file is a GNU parallel extension to the Standard C++ Library.