import scala.util.Random

class QuickSort { // main entry of sort algorithm

  //partial insert sort

  def insertsort(array: Array[Int], lo: Int, hi: Int): Unit = {
    var i: Int = lo
    while (i <= hi) {
      var j: Int = i
      while (j > lo) {
        if (array(j) < array(j - 1)) swap(array, j, j - 1)
        j -= 1
      }
      i += 1
    }
  }

  private val cutoff = 6

  def quicksort(array: Array[Int]): Unit = {
    shuffling(array)
    sort(array, 0, array.length - 1)
  }

  // shuffling for performance guarantee
  private def shuffling(array: Array[Int]): Unit = {
    var i: Int = 0
    while (i < array.length) {
      val r: Random = new Random
      val j: Int = r.nextInt(i + 1)
      if (i != j) swap(array, i, j)
      i += 1
    }
  }

  // recursive sort// recursive sort

  private def sort(array: Array[Int], low: Int, high: Int): Unit = { // improvement #1
    if (high <= low + cutoff) {
      insertsort(array, low, high)
      return
    }
    // improvement #2
    median3(array, low, high)
    //    ------trational partition-----
    //      // get pivot
    //      int pivot = partition(array, low, high);
    //      // recursive sort
    //      sort(array, low, pivot - 1);
    //      sort(array, pivot + 1, high);
    //    ------3 way partition version--------
    val pivots: Array[Int] = partition3(array, low, high)
    val lt: Int = pivots(0)
    val gt: Int = pivots(1)
    sort(array, low, lt - 1)
    sort(array, gt + 1, high)
  }

  // partition// partition

  private def partition(array: Array[Int], low: Int, high: Int) = {
    val pivotValue: Int = array(low)
    var i: Int = low
    var j: Int = high + 1

    var outerCtrl: Boolean = true

    while (outerCtrl) {
      var greaterCtrl = true
      //find the first one greater than pivotValue (left-to-right scan)
      i += 1
      while ( greaterCtrl && (array(i) < pivotValue)) if (i == high) greaterCtrl = false

      var lessCtrl = true
      //find the first one less than pivotValue (right-to-left scan)
      j -= 1
      while (lessCtrl && (array(j) > pivotValue)) if (j == low) lessCtrl = false

      if (i >= j) outerCtrl = false else swap(array, i, j) //swap them to keep order
    }
    //put pivot to the right place, j will remember the location for pivot
    swap(array, low, j)
    //return the position of pivot
    j
  }

  private def partition3(array: Array[Int], lo: Int, hi: Int): Array[Int] = {
    //compare with normal partition//compare with normal partition

    //we need two more variables: lt, gt
    //lt: the first element with the pivot value
    //the last element with pivot value

    var lt: Int = lo
    var gt: Int = hi
    val cmp: Int = array(lo)
    var i: Int = lo

    var ctrl: Boolean = true
    while (ctrl) {
      if (array(i) < cmp) {
        swap(array, i, lt)
        i += 1
        lt += 1
      } else if (array(i) > cmp) {
        swap(array, i, gt)
        gt -= 1
      } else i += 1

      if(i > gt) ctrl = false
    }

    Array[Int](lt, gt)
  }


  // swap
  private def swap(array: Array[Int], index1: Int, index2: Int): Unit = {
    val swap: Int = array(index2)
    array(index2) = array(index1)
    array(index1) = swap
  }

  def median3(array: Array[Int], lo: Int, hi: Int): Unit = {
    val mid = lo + (hi - lo) / 2
    if (array(lo) > array(hi)) swap(array, lo, hi)
    if (array(mid) > array(hi)) swap(array, mid, hi)
    if (array(mid) < array(lo)) swap(array, lo, mid)
    swap(array, mid, lo)
  }

}