text: 'use strict';
  /* @flow */
  
  module.exports = quickselect;
  
  /**
   * Rearrange items in `arr` so that all items in `[left, k]` range are the smallest.
   * The `k`-th element will have the `(k - left + 1)`-th smallest value in `[left, right]`.
   *
   * Implements Floyd-Rivest selection algorithm https://en.wikipedia.org/wiki/Floyd-Rivest_algorithm
   *
   * @private
   * @param {Array<number>} arr input array
   * @param {number} k pivot index
   * @param {number} left left index
   * @param {number} right right index
   * @returns {undefined}
   * @example
   * var arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39];
   * quickselect(arr, 8);
   * // [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95]
   */
  function quickselect(arr /*: Array<number> */, k /*: number */, left /*: number */, right /*: number */) {
      left = left || 0;
      right = right || (arr.length - 1);
  
      while (right > left) {
          // 600 and 0.5 are arbitrary constants chosen in the original paper to minimize execution time
          if (right - left > 600) {
              var n = right - left + 1;
              var m = k - left + 1;
              var z = Math.log(n);
              var s = 0.5 * Math.exp(2 * z / 3);
              var sd = 0.5 * Math.sqrt(z * s * (n - s) / n);
              if (m - n / 2 < 0) sd *= -1;
              var newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
              var newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
              quickselect(arr, k, newLeft, newRight);
          }
  
          var t = arr[k];
          var i = left;
          var j = right;
  
          swap(arr, left, k);
          if (arr[right] > t) swap(arr, left, right);
  
          while (i < j) {
              swap(arr, i, j);
              i++;
              j--;
              while (arr[i] < t) i++;
              while (arr[j] > t) j--;
          }
  
          if (arr[left] === t) swap(arr, left, j);
          else {
              j++;
              swap(arr, j, right);
          }
  
          if (j <= k) left = j + 1;
          if (k <= j) right = j - 1;
      }
  }
  
  function swap(arr, i, j) {
      var tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
  }
  