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