def main(args: Array[String]) = {

    val xxxxx = 1
    xxxxx = 2
    val a = 0
    val b = 3
    if(a > b) {
        println(b)
    } else {
        println(a)
    }

    val input = scala.io.StdIn.readLine()
    val output = 0
    println(output)

    if(a > b) {
        if(a > b) {
            if(a > b) {
                if(a > b) {
                    if(a > b) {
                        if(a > b) {
                            println(a)
                        }
                    }
                }
            }
        }
    }

    for(i <- 0 to 5) {
        if(a > b) {
            if(a > b) {
                if(a > b) {
                    println("a > b")
                }
            }
        }
    }

    val x = 11

    x match {
      case 0 =>
          "zero"
      case 1 =>
          "one"
      case 2 =>
          "two"
      case 3 =>
          "three"
      case 4 =>
          "four"
      case 5 =>
          "five"
    }

    val array1 = Array(3, 6, 1, 5, 2, 0, 8)
    bubbleSort1(array1)

    val array2 = Array(4, 6, 22, 56, 11, 55, 223, 1, 7, 33, 9, 10, 67, 88, 2, 5, 6, 9, 213, 6, 3)
    bubbleSort2(array2)

    val array3 = Array(4, 6, 11, 55, 223, 1, 7, 33, 9, 10, 67, 88, 2, 5, 6, 9, 213, 6, 3)
    bubbleSort(array3)

    val array5 = Array(4, 6, 22, 56, 11, 55, 223, 1, 7, 6, 3, 0, 1, 2, 3)
    recursiveInsertionSort(array5)

    val array6 = Array(4, 6, 22, 56, 55, 223, 43, 23, 1, 7, 6, 3)
    selectionSort(array6)

    val array7 = Array(4, 6, 22, 56, 11, 3)
    insertionSort(array7)

    val array8 = Array(56, 11, 55, 223, 1, 7, 6, 3)
    mergeSort(array8)

}

def bubbleSort(numbers: Array[Int]) = {
    for(k <- 1 until numbers.length; j <- 0 until numbers.length - 1) {
        if (numbers(j) > numbers(j + 1)) {
            val x = numbers(j)
            numbers(j) = numbers(j + 1)
            numbers(j + 1) = x
        }
    }
}

def bubbleSort2(numbers: Array[Int]) = {
    for(k <- 1 until numbers.length; j <- 0 until numbers.length - 1 if numbers(j) > numbers(j+1)) {
        (numbers(j), numbers(j + 1)) match {
            case (x, y) =>
            numbers(j) = y
            numbers(j + 1) = x
        }
    }
}

def bubbleSort3(numbers: Array[Int]) = {
    for(k <- 1 until numbers.length; j <- 0 until numbers.length - k
        if(numbers(j) > numbers(j + 1)) {
            val x = numbers(j)
            numbers(j) = numbers(j + 1)
            numbers(j + 1) = x
    }
}

def fibonacci(userInput: Int) = {
    var temp1, temp2 = 1;
    var result = 0;
    for (i <- 3 to userInput) {
        result = temp1 + temp2;
        temp1 = temp2;
        temp2 = result;
        i + userInput;
    }
}

def recursiveInsertionSort(array: List[Int]): List[Int] = {

    def insertion(x: List[Int]): List[Int] = {
        x match {
            case List() => List()
            case x :: xs => ins(x, insertion(xs))
        }
    }

    def ins(x: Int, xs: List[Int]): List[Int] = {
        xs match {
            case List() => List(x)
            case x2 :: xs2 => if(x <= x2) x :: xs else x2 :: ins(x, xs2)
        }
    }

    insertion(array)
}

def selectionSort(array: Array[Int]): Array[Int] = {

    for(i <- 0 to array.length - 1) {
        var min: Int = i
        var minVal = array(i)

        for(j <- i + 1 to array.length - 1) {
            if(array(j) < minVal) {
                min = j
                minVal = array(j)
            }
        }
        val temp: Int = array(i)
        array(i) = array(min)
        array(min) = temp
    }
    array
}

def insertionSort(array: Array[Int]): Array[Int] = {
    for(i <- 0 to array.length - 1) {
        val temp: Int = array(i)
        var j = i - 1
        while(j >= 0 && temp < array(j)) {
            array(j + 1) = array(j)
            j -= 1
        }
        array(j + 1) = temp
    }
    array
}

def mergeSort(array: Array[Int]): Array[Int] = {

    def sort(array: Array[Int]): Array[Int] = {
        MS(array, 0, array.length - 1)
    }

    def MS(array: Array[Int], low: Int, high: Int): Array[Int] = {
        if(low < high) {
            val mid = (low + high) / 2
            MS(array, low, mid)
            MS(array, mid + 1, high)
            merge(array, low, mid, high)
        } else {
            array
        }
    }

    def merge(array: Array[Int], low: Int, mid: Int, high: Int): Array[Int] = {

        val left = array.slice(low, mid + 1)
        val right = array.slice(mid + 1, high + 1)

        var i = 0
        var j = 0
        var k = low
        while(k < high + 1) {
            if(i > left.length - 1) {
                array(k) = right(j)
                j = j + 1
            } else if(j > right.length - 1) {
                array(k) = left(i)
                i = i + 1
            } else if(left(i) <= right(j)) {
                array(k) = left(i)
                i = i + 1
            } else {
                array(k) = right(j)
                j = j + 1
            }
            k = k + 1
        }
        array
    }
    sort(array)
}