3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/sort.h
32 * @brief Parallel sorting algorithm switch.
33 * This file is a GNU parallel extension to the Standard C++ Library.
36 // Written by Johannes Singler.
38 #ifndef _GLIBCXX_PARALLEL_SORT_H
39 #define _GLIBCXX_PARALLEL_SORT_H 1
41 #include <parallel/basic_iterator.h>
42 #include <parallel/features.h>
43 #include <parallel/parallel.h>
45 #if _GLIBCXX_ASSERTIONS
46 #include <parallel/checkers.h>
49 #if _GLIBCXX_MERGESORT
50 #include <parallel/multiway_mergesort.h>
53 #if _GLIBCXX_QUICKSORT
54 #include <parallel/quicksort.h>
57 #if _GLIBCXX_BAL_QUICKSORT
58 #include <parallel/balanced_quicksort.h>
61 namespace __gnu_parallel
64 * @brief Choose a parallel sorting algorithm.
65 * @param begin Begin iterator of input sequence.
66 * @param end End iterator of input sequence.
67 * @param comp Comparator.
68 * @param stable Sort stable.
71 template<typename RandomAccessIterator
, typename Comparator
>
73 parallel_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
74 Comparator comp
, bool stable
)
76 _GLIBCXX_CALL(end
- begin
)
77 typedef std::iterator_traits
<RandomAccessIterator
> traits_type
;
78 typedef typename
traits_type::value_type value_type
;
79 typedef typename
traits_type::difference_type difference_type
;
83 difference_type n
= end
- begin
;
86 #if _GLIBCXX_MERGESORT
89 if(_Settings::get().sort_splitting
== EXACT
)
90 parallel_sort_mwms
<true, true>
91 (begin
, end
, comp
, get_max_threads());
93 parallel_sort_mwms
<true, false>
94 (begin
, end
, comp
, get_max_threads());
96 else if (_Settings::get().sort_algorithm
== MWMS
)
98 if(_Settings::get().sort_splitting
== EXACT
)
99 parallel_sort_mwms
<false, true>
100 (begin
, end
, comp
, get_max_threads());
102 parallel_sort_mwms
<false, false>
103 (begin
, end
, comp
, get_max_threads());
106 #if _GLIBCXX_QUICKSORT
107 else if (!stable
&& _Settings::get().sort_algorithm
== QS
)
108 parallel_sort_qs(begin
, end
, comp
, n
, get_max_threads());
110 #if _GLIBCXX_BAL_QUICKSORT
111 else if (!stable
&& _Settings::get().sort_algorithm
== QS_BALANCED
)
112 parallel_sort_qsb(begin
, end
, comp
, n
, get_max_threads());
115 __gnu_sequential::stable_sort(begin
, end
, comp
);
117 __gnu_sequential::sort(begin
, end
, comp
);
120 } // end namespace __gnu_parallel