| 127 | /// Standard quick sort |
| 128 | template<class Type, class Less> |
| 129 | inline void |
| 130 | quicksort(Type* l, Type* r, Less &less) { |
| 131 | QuickSortStack<Type> s; |
| 132 | while (true) { |
| 133 | std::swap(*(l+((r-l) >> 1)),*(r-1)); |
| 134 | exchange(*l,*(r-1),less); |
| 135 | exchange(*l,*r,less); |
| 136 | exchange(*(r-1),*r,less); |
| 137 | Type* i = partition(l+1,r-1,less); |
| 138 | if (i-l > r-i) { |
| 139 | if (r-i > QuickSortCutoff) { |
| 140 | s.push(l,i-1); l=i+1; continue; |
| 141 | } |
| 142 | if (i-l > QuickSortCutoff) { |
| 143 | r=i-1; continue; |
| 144 | } |
| 145 | } else { |
| 146 | if (i-l > QuickSortCutoff) { |
| 147 | s.push(i+1,r); r=i-1; continue; |
| 148 | } |
| 149 | if (r-i > QuickSortCutoff) { |
| 150 | l=i+1; continue; |
| 151 | } |
| 152 | } |
| 153 | if (s.empty()) |
| 154 | break; |
| 155 | s.pop(l,r); |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | /// Comparison class for sorting using \a < |
| 160 | template<class Type> |