////////////////////////////////////////////////
// Modified so that this can be copy and pasted to my Sorting.scala file

private def insertionSort2(a: Array[Master.ElemType], i0: Int, iN: Int): Unit = {
    val n = iN - i0
    if (n < 2) return
    if (a(i0) > a(i0+1)) {
      val temp = a(i0)
      a(i0) = a(i0+1)
      a(i0+1) = temp
    }
    var m = 2
    while (m < n) {
      // Speed up already-sorted case by checking last element first
      val next = a(i0 + m)
      if (next < a(i0+m-1)) {
        var iA = i0
        var iB = i0 + m - 1
        while (iB - iA > 1) {
          val ix = (iA + iB) >>> 1    // Use bit shift to get unsigned div by 2
          if (next < a(ix)) iB = ix
          else iA = ix
        }
        val ix = iA + (if (next < a(iA)) 0 else 1)
        var i = i0 + m
        while (i > ix) {
          a(i) = a(i-1)
          i -= 1
        }
        a(ix) = next
      }
      m += 1
    }
  }

  def quicksort2(a: Array[Master.ElemType]): Unit = {
	val qsortThreshold = 16
    // Must have iN >= i0 or math will fail.  Also, i0 >= 0.
    def inner(a: Array[Master.ElemType], i0: Int, iN: Int): Unit = {
      if (iN - i0 < qsortThreshold) insertionSort2(a, i0, iN)
      else {
        val iK = (i0 + iN) >>> 1    // Unsigned div by 2
        // Find index of median of first, central, and last elements
        var pL =
          if (a(i0) <= a(iN - 1))
            if (a(i0) < a(iK))
              if (a(iN - 1) < a(iK)) iN - 1 else iK
            else i0
          else
            if (a(i0) < a(iK)) i0
            else
              if (a(iN - 1) <= a(iK)) iN - 1
              else iK
        val pivot = a(pL)
        // pL is the start of the pivot block; move it into the middle if needed
        if (pL != iK) { a(pL) = a(iK); a(iK) = pivot; pL = iK }
        // Elements equal to the pivot will be in range pL until pR
        var pR = pL + 1
        // Items known to be less than pivot are below iA (range i0 until iA)
        var iA = i0
        // Items known to be greater than pivot are at or above iB (range iB until iN)
        var iB = iN
        // Scan through everything in the buffer before the pivot(s)
        while (pL - iA > 0) {
          val current = a(iA)
         (current - pivot) match {
            case 0 =>
              // Swap current out with pivot block
              a(iA) = a(pL - 1)
              a(pL - 1) = current
              pL -= 1
            case x if x < 0 =>
              // Already in place.  Just update indices.
              iA += 1
            case _ if iB > pR =>
              // Wrong side.  There's room on the other side, so swap
              a(iA) = a(iB - 1)
              a(iB - 1) = current
              iB -= 1
            case _ =>
              // Wrong side and there is no room.  Swap by rotating pivot block.
              a(iA) = a(pL - 1)
              a(pL - 1) = a(pR - 1)
              a(pR - 1) = current
              pL -= 1
              pR -= 1
              iB -= 1
          }
        }
        // Get anything remaining in buffer after the pivot(s)
        while (iB - pR > 0) {
          val current = a(iB - 1)
          (current - pivot) match {
            case 0 =>
              // Swap current out with pivot block
              a(iB - 1) = a(pR)
              a(pR) = current
              pR += 1
            case x if x > 0 =>
              // Already in place.  Just update indices.
              iB -= 1
            case _ =>
              // Wrong side and we already know there is no room.  Swap by rotating pivot block.
              a(iB - 1) = a(pR)
              a(pR) = a(pL)
              a(pL) = current
              iA += 1
              pL += 1
              pR += 1
          }
        }
        // Use tail recursion on large half (Sedgewick's method) so we don't blow up the stack if pivots are poorly chosen
        if (iA - i0 < iN - iB) {
          inner(a, i0, iA)  // True recursion
          inner(a, iB, iN)  // Should be tail recursion
        }
        else {
          inner(a, iB, iN)  // True recursion
          inner(a, i0, iA)  // Should be tail recursion
        }
      }
    }
    inner(a, 0, a.length)
  }