Sorting for Scala

sorting.scala

def inPlcaeSelectionSort(xs: Array[Int]): Array[Int] = {

  def findMinLocation(offset: Int): Int = {
    var currentMin = Int.MaxValue
    var currentMinIndex = 0
    for (i <- offset until xs.size) {
      if (xs(i) < currentMin) {
        currentMin = xs(i)
        currentMinIndex = i
      }
    }
    currentMinIndex
  }

  for (i <- 0 until xs.size) {
    val minLocation = findMinLocation(i)
    val tmp = xs(i)
    xs(i) = xs(minLocation)
    xs(minLocation) = tmp
  }
  
  xs

}

def quicksort(xs: List[Int]): List[Int] = {

  xs.size match {
    case 0|1 => xs      // 如果是空的或者只一個就是已經排好了
    case n   =>
      val pivot = xs(xs.size / 2)
      val largeThanPivot = xs.filter(_ > pivot)
      val sameAsPivot = xs.filter(_ == pivot)
      val smallThanPivot = xs.filter(_ < pivot)

      quicksort(smallThanPivot) ++ 
      sameAsPivot ++
      quicksort(largeThanPivot)
  }
}


def mergeSort(xs: List[Int]): List[Int] = {

  def mergeByLoop(xs: List[Int], ys: List[Int]): List[Int] = {
    (xs, ys) match {
      case (Nil, Nil) => Nil
      case (_, Nil)   => xs
      case (Nil, _)   => ys
      case (_, _) =>
        var xIndex = xs.size - 1
        var yIndex = ys.size - 1
        var result: List[Int] = Nil
        while (result.size < xs.size + ys.size) {
  
          if (xIndex < 0 && yIndex >= 0) {
            result ::= ys(yIndex)
            yIndex -= 1
          } else if (yIndex < 0 && xIndex >= 0) {
            result ::= xs(xIndex)
            xIndex -= 1
          } else if (xIndex >= 0 && yIndex >= 0) {
            if (xs(xIndex) >= ys(yIndex)) {
              result ::= xs(xIndex)
              xIndex -= 1
            } else {
              result ::= ys(yIndex)
              yIndex -= 1
            }
          }
  
        }
        result
    }
  }

  def mergeByRecursive(xs: List[Int], ys: List[Int]): List[Int] = {
    (xs, ys) match {
      case (_, Nil) => xs
      case (Nil, _) => ys
      case (x :: xsRemain, y :: ysRemain) =>
        if (x > y) {
          y :: merge(xs, ysRemain)
        } else {
          x :: merge(xsRemain, ys)
        }
    }
  }

  if (xs.size <= 1) {
    xs
  } else {
    val (ys, zs) = xs.splitAt(xs.size / 2)
    mergeByRecursive(mergeSort(ys), mergeSort(zs))
  }
}