basic-quick-sort.scala

def quickSort(xs: Array[Int]) {
  def sort1(l: Int, r: Int) {
    val pivot = xs((l + r) / 2)
    var i = l;
    var j = r;

    while (i <= j) {
      while (xs(i) < pivot) {
        i += 1
      }

      while (xs(j) > pivot) {
        j -= 1
      }

      if (i <= j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }

    if (l < j) {
      sort1(l, j)
    }

    if (j < r) {
      sort1(i, r)
    }
  }

  def swap(i: Int, j: Int) {
    val t = xs(i)
    xs(i) = xs(j)
    xs(j) = t
  }

  sort1(0, (xs.length - 1))
}