91       for (i = e; i > pos; i--) {  /* move up elements */  in tinsert()
305 ** precondition: a[lo] <= P == a[up-1] <= a[up],
306 ** so it only needs to do the partition from lo + 1 to up - 2.
307 ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up]
310 static IdxT partition (lua_State *L, IdxT lo, IdxT up) {  in partition()  argument
312   IdxT j = up - 1;  /* will be decremented before first use */  in partition()
313   /* loop invariant: a[lo .. i] <= P <= a[j .. up] */  in partition()
317       if (i == up - 1)  /* a[i] < P  but a[up - 1] == P  ?? */  in partition()
328     /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */  in partition()
330       /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */  in partition()
332       /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */  in partition()
333       set2(L, up - 1, i);  in partition()
343 ** Choose an element in the middle (2nd-3th quarters) of [lo,up]
346 static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) {  in choosePivot()  argument
347   IdxT r4 = (up - lo) / 4;  /* range/4 */  in choosePivot()
349   lua_assert(lo + r4 <= p && p <= up - r4);  in choosePivot()
357 static void auxsort (lua_State *L, IdxT lo, IdxT up,  in auxsort()  argument
359   while (lo < up) {  /* loop for tail recursion */  in auxsort()
362     /* sort elements 'lo', 'p', and 'up' */  in auxsort()
364     lua_geti(L, 1, up);  in auxsort()
365     if (sort_comp(L, -1, -2))  /* a[up] < a[lo]? */  in auxsort()
366       set2(L, lo, up);  /* swap a[lo] - a[up] */  in auxsort()
369     if (up - lo == 1)  /* only 2 elements? */  in auxsort()
371     if (up - lo < RANLIMIT || rnd == 0)  /* small interval or no randomize? */  in auxsort()
372       p = (lo + up)/2;  /* middle element is a good pivot */  in auxsort()
374       p = choosePivot(lo, up, rnd);  in auxsort()
381       lua_geti(L, 1, up);  in auxsort()
382       if (sort_comp(L, -1, -2))  /* a[up] < a[p]? */  in auxsort()
383         set2(L, p, up);  /* swap a[up] - a[p] */  in auxsort()
387     if (up - lo == 2)  /* only 3 elements? */  in auxsort()
391     lua_geti(L, 1, up - 1);  /* push a[up - 1] */  in auxsort()
392     set2(L, p, up - 1);  /* swap Pivot (a[p]) with a[up - 1] */  in auxsort()
393     p = partition(L, lo, up);  in auxsort()
394     /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */  in auxsort()
395     if (p - lo < up - p) {  /* lower interval is smaller? */  in auxsort()
398       lo = p + 1;  /* tail call for [p + 1 .. up] (upper interval) */  in auxsort()
401       auxsort(L, p + 1, up, rnd);  /* call recursively for upper interval */  in auxsort()
402       n = up - p;  /* size of smaller interval */  in auxsort()
403       up = p - 1;  /* tail call for [lo .. p - 1]  (lower interval) */  in auxsort()
405     if ((up - lo) / 128 > n) /* partition too imbalanced? */  in auxsort()
407   }  /* tail call auxsort(L, lo, up, rnd) */  in auxsort()