abkfenris / sugarloaf

      //   1) for x in ]left, less[ : x < pivot.

      //   2) for x in [less, k[ : x == pivot.

      //   3) for x in ]great, right[ : x > pivot.

      for (var k = less; k <= great; ++k) {

        var ek = a[k], xk = f(ek);

        if (xk < pivotValue1) {

          if (k !== less) {

            a[k] = a[less];

            a[less] = ek;

          }

          ++less;

        } else if (xk > pivotValue1) {

          // Find the first element <= pivot in the range [k - 1, great] and

          // put [:ek:] there. We know that such an element must exist:

          // When k == less, then el3 (which is equal to pivot) lies in the

          // interval. Otherwise a[k - 1] == pivot and the search stops at k-1.

          // Note that in the latter case invariant 2 will be violated for a

          // short amount of time. The invariant will be restored when the

          // pivots are put into their final positions.

          while (true) {

            var greatValue = f(a[great]);

            if (greatValue > pivotValue1) {

              great--;

              // This is the only location in the while-loop where a new

              // iteration is started.

              continue;

            } else if (greatValue < pivotValue1) {

              // Triple exchange.

              a[k] = a[less];

              a[less++] = a[great];

              a[great--] = ek;

              break;

            } else {

              a[k] = a[great];

              a[great--] = ek;

              // Note: if great < k then we will exit the outer loop and fix

              // invariant 2 (which we just violated).

              break;

            }

          }

        }

      }

    } else {

      // We partition the list into three parts:

      //   1. for x in [ *, less[ : x == pivot1

      //   2. for x in [less, k[ : pivot1 < x && x < pivot2

      //   3. for x in ]great, * ] : x == pivot2

      for (var k = less; k <= great; k++) {

        var ek = a[k], xk = f(ek);

        if (xk <= pivotValue1 && xk >= pivotValue1) {

          if (k !== less) {

            a[k] = a[less];

            a[less] = ek;

          }

          less++;

        } else {

          if (xk <= pivotValue2 && xk >= pivotValue2) {

            while (true) {

              var greatValue = f(a[great]);

              if (greatValue <= pivotValue2 && greatValue >= pivotValue2) {

                great--;

                if (great < k) break;

                // This is the only location inside the loop where a new

                // iteration is started.

                continue;

              } else {

                // a[great] < pivot2.

                if (greatValue < pivotValue1) {

                  // Triple exchange.

                  a[k] = a[less];

                  a[less++] = a[great];

                  a[great--] = ek;

                } else {

                  // a[great] == pivot1.

                  a[k] = a[great];

                  a[great--] = ek;

                }

                break;

              }

            }

          }

        }

      }

    }

    // The second partition has now been cleared of pivot elements and looks

      //   1. for x in ]left, less[ : x < pivot1

      //   2. for x in [less, k[ : pivot1 <= x && x <= pivot2

      //   3. for x in ]great, right[ : x > pivot2

      for (var k = less; k <= great; k++) {

        var ek = a[k], xk = f(ek);

        if (xk < pivotValue1) {

          if (k !== less) {

            a[k] = a[less];

            a[less] = ek;

          }

          ++less;

        } else {

          if (xk > pivotValue2) {

            while (true) {

              var greatValue = f(a[great]);

              if (greatValue > pivotValue2) {

                great--;

                if (great < k) break;

                // This is the only location inside the loop where a new

                // iteration is started.

                continue;

              } else {

                // a[great] <= pivot2.

                if (greatValue < pivotValue1) {

                  // Triple exchange.

                  a[k] = a[less];

                  a[less++] = a[great];

                  a[great--] = ek;

                } else {

                  // a[great] >= pivot1.

                  a[k] = a[great];

                  a[great--] = ek;

                }

                break;

              }

            }

          }

        }

      }

    }

    // Move pivots into their final positions.