| 184 | } |
| 185 | |
| 186 | static void auxsort (lua_State *L, int l, int u) { |
| 187 | while (l < u) { /* for tail recursion */ |
| 188 | int i, j; |
| 189 | /* sort elements a[l], a[(l+u)/2] and a[u] */ |
| 190 | lua_rawgeti(L, 1, l); |
| 191 | lua_rawgeti(L, 1, u); |
| 192 | if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ |
| 193 | set2(L, l, u); /* swap a[l] - a[u] */ |
| 194 | else |
| 195 | lua_pop(L, 2); |
| 196 | if (u-l == 1) break; /* only 2 elements */ |
| 197 | i = (l+u)/2; |
| 198 | lua_rawgeti(L, 1, i); |
| 199 | lua_rawgeti(L, 1, l); |
| 200 | if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */ |
| 201 | set2(L, i, l); |
| 202 | else { |
| 203 | lua_pop(L, 1); /* remove a[l] */ |
| 204 | lua_rawgeti(L, 1, u); |
| 205 | if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ |
| 206 | set2(L, i, u); |
| 207 | else |
| 208 | lua_pop(L, 2); |
| 209 | } |
| 210 | if (u-l == 2) break; /* only 3 elements */ |
| 211 | lua_rawgeti(L, 1, i); /* Pivot */ |
| 212 | lua_pushvalue(L, -1); |
| 213 | lua_rawgeti(L, 1, u-1); |
| 214 | set2(L, i, u-1); |
| 215 | /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ |
| 216 | i = l; j = u-1; |
| 217 | for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ |
| 218 | /* repeat ++i until a[i] >= P */ |
| 219 | while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) { |
| 220 | if (i>=u) luaL_error(L, "invalid order function for sorting"); |
| 221 | lua_pop(L, 1); /* remove a[i] */ |
| 222 | } |
| 223 | /* repeat --j until a[j] <= P */ |
| 224 | while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) { |
| 225 | if (j<=l) luaL_error(L, "invalid order function for sorting"); |
| 226 | lua_pop(L, 1); /* remove a[j] */ |
| 227 | } |
| 228 | if (j<i) { |
| 229 | lua_pop(L, 3); /* pop pivot, a[i], a[j] */ |
| 230 | break; |
| 231 | } |
| 232 | set2(L, i, j); |
| 233 | } |
| 234 | lua_rawgeti(L, 1, u-1); |
| 235 | lua_rawgeti(L, 1, i); |
| 236 | set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */ |
| 237 | /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ |
| 238 | /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ |
| 239 | if (i-l < u-i) { |
| 240 | j=l; i=i-1; l=i+2; |
| 241 | } |
| 242 | else { |
| 243 | j=i+1; i=u; u=j-2; |
no test coverage detected