Quick.scala

object Quick {  
  def sort(xs: Array[Int]): Unit = {
    def go(start: Int, end: Int): Unit = {
      if (end - start > 1) {
        val i = partition(start, end)
        go(start, i)
        go(i + 1, end)
      }
    }

    def partition(start: Int, end: Int): Int = {
      require(end - start > 1, "Doesn't make sense to partition an array with fewer than two elements.")
      val pivot = xs(start)
      var l = start + 1
      var r = l
      def checkInvariant(stage: String): Unit = {
        assert(xs.slice(start, l).forall(_ <= pivot), s"$start...$l should be <= pivot $pivot")
        assert(xs.slice(l, r).forall(_ > pivot), s"$l...$r should be > pivot $pivot")
      }
      checkInvariant("initialization")
      while (r < end) {
        if (xs(r) <= pivot) {
          swap(xs, r, l)
          l += 1
        }
        r += 1
        checkInvariant("maintenance")
      }
      // At this point: xs.slice(start, l) <= pivot, xs.slice(l, end) > pivot
      // So we can move the pivot to the end of the <= slice, at position l - 1.
      swap(xs, start, l - 1)
      l - 1
    }

    go(0, xs.length)
  }
}