| 94 | /// Standard insertion sort |
| 95 | template<class Type, class Less> |
| 96 | forceinline void |
| 97 | insertion(Type* l, Type* r, Less &less) { |
| 98 | for (Type* i = r; i > l; i--) |
| 99 | exchange(*(i-1),*i,less); |
| 100 | for (Type* i = l+2; i <= r; i++) { |
| 101 | Type* j = i; |
| 102 | Type v = *i; |
| 103 | while (less(v,*(j-1))) { |
| 104 | *j = *(j-1); j--; |
| 105 | } |
| 106 | *j = v; |
| 107 | } |
| 108 | } |
| 109 | |
| 110 | /// Standard partitioning |
| 111 | template<class Type, class Less> |