Merge sort Recursive

object Main extends App {
  def quickSort (array: Array[Int], left: Int = 0, right: Int): Array[Int] = {
    if(left >= right) array
    val pivot = right
    val pivotPosition = partition(array, pivot, left, right)
    //sort left and right
    quickSort1(array, left, pivotPosition - 1)
    quickSort1(array, pivotPosition + 1, right)
  }

  def quickSort1(array: Array[Int], left:Int, right:Int): Array[Int] = {
    if(left < right) {
      val pivot = right
      val partitionIndex = partition(array, pivot, left, right)

      //sort left and right
      quickSort1(array, left, partitionIndex - 1)
      quickSort1(array, partitionIndex + 1, right)
    }
    array
  }

  private def partition(array: Array[Int], pivot: Int, left: Int, right: Int):Int = {
    val pivotValue = array(pivot)
    var partitionIndex = left

    for(i <- left to right) {
      if(array(i) < pivotValue){
        swap(array, i, partitionIndex)
        partitionIndex = partitionIndex+1
      }
    }
    swap(array, right, partitionIndex)
    partitionIndex
  }

  private def swap(array: Array[Int], firstIndex: Int, secondIndex: Int){
    var temp = array(firstIndex)
    array(firstIndex) = array(secondIndex)
    array(secondIndex) = temp;
  }

  val numbers = Array(-1, 10, 5, 3, 3, -10, 7, -2, 20, 100, -5, 1002,-100)

  println(quickSort(numbers, 0, numbers.length - 1).toList)
  println(quickSort1(numbers, 0, numbers.length - 1).toList)
}