58 if (first == last) { |
64 if (first == last) { |
59 return first; |
65 return first; |
60 } |
66 } |
61 std::iter_swap(first, last); |
67 std::iter_swap(first, last); |
62 ++first; |
68 ++first; |
63 if (!(first < last)) { |
|
64 return first; |
|
65 } |
|
66 while (true) { |
69 while (true) { |
67 while (!(functor(*first) & mask)) { |
70 while (!(functor(*first) & mask)) { |
68 ++first; |
71 ++first; |
69 } |
72 } |
70 --last; |
73 --last; |
71 while (functor(*last) & mask) { |
74 while (functor(*last) & mask) { |
72 --last; |
75 --last; |
73 } |
76 } |
74 if (!(first < last)) { |
77 if (unitRange(last, first)) { |
75 return first; |
78 return first; |
76 } |
79 } |
77 std::iter_swap(first, last); |
80 std::iter_swap(first, last); |
78 ++first; |
81 ++first; |
79 } |
82 } |
95 if (first == last) { |
98 if (first == last) { |
96 return first; |
99 return first; |
97 } |
100 } |
98 std::iter_swap(first, last); |
101 std::iter_swap(first, last); |
99 ++first; |
102 ++first; |
100 if (!(first < last)) { |
|
101 return first; |
|
102 } |
|
103 while (true) { |
103 while (true) { |
104 while (functor(*first) < 0) { |
104 while (functor(*first) < 0) { |
105 ++first; |
105 ++first; |
106 } |
106 } |
107 --last; |
107 --last; |
108 while (functor(*last) >= 0) { |
108 while (functor(*last) >= 0) { |
109 --last; |
109 --last; |
110 } |
110 } |
111 if (!(first < last)) { |
111 if (unitRange(last, first)) { |
112 return first; |
112 return first; |
113 } |
113 } |
114 std::iter_swap(first, last); |
114 std::iter_swap(first, last); |
115 ++first; |
115 ++first; |
116 } |
116 } |
117 } |
117 } |
118 |
118 |
119 template <typename Value, typename Iterator, typename Functor> |
119 template <typename Value, typename Iterator, typename Functor> |
120 void radixIntroSort(Iterator first, Iterator last, |
120 void radixIntroSort(Iterator first, Iterator last, |
121 Functor functor, Value mask) { |
121 Functor functor, Value mask) { |
122 while (mask != 0 && last - first > 1) { |
122 while (mask != 0 && first != last && !unitRange(first, last)) { |
123 Iterator cut = radixSortPartition(first, last, functor, mask); |
123 Iterator cut = radixSortPartition(first, last, functor, mask); |
124 mask >>= 1; |
124 mask >>= 1; |
125 radixIntroSort(first, cut, functor, mask); |
125 radixIntroSort(first, cut, functor, mask); |
126 first = cut; |
126 first = cut; |
127 } |
127 } |