| 34 | // than those in [pos, last). |
| 35 | template <typename T, class Compare> |
| 36 | void DivideAtPos(std::vector<T>& x, Compare& comp, int first, int last, |
| 37 | int pos) { |
| 38 | if (first > pos || pos >= last) return; |
| 39 | VLOG(2) << "[Sorter] Divide " << first << " to " << last << " at " << pos; |
| 40 | |
| 41 | int i = first, j = last - 1; |
| 42 | T pivot = x[pos]; |
| 43 | while (true) { |
| 44 | while (i <= j && comp(x[i], pivot)) ++i; |
| 45 | while (i <= j && !comp(x[j], pivot)) --j; |
| 46 | if (i >= j) break; |
| 47 | std::swap(x[i], x[j]); |
| 48 | ++i; |
| 49 | --j; |
| 50 | } |
| 51 | if (i >= last) { |
| 52 | i = last - 1; |
| 53 | std::swap(x[pos], x[i]); |
| 54 | } |
| 55 | if (j < first) { |
| 56 | std::swap(x[pos], x[first]); |
| 57 | i = first + 1; |
| 58 | } |
| 59 | if (i == pos) return; |
| 60 | if (i > pos) { |
| 61 | DivideAtPos(x, comp, first, i, pos); |
| 62 | } else { |
| 63 | DivideAtPos(x, comp, i, last, pos); |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | } // namespace |
| 68 | |