fun main() {
    val array = arrayOf(3, 5, 1, 8, 9, 0)
        val sortedArray = quicksort(array, 0, array.size - 1)
        sortedArray.forEach {
            println(it)
        }
}

private fun quicksort(array: Array<Int>, first: Int, last: Int): Array<Int> {
        var i = first
        var j = last
        var sortedArray = array
        val pivot = (sortedArray[i] + sortedArray[j]) / 2

        while (i < j) {
            while (sortedArray[i] < pivot) {
                i += 1
            }

            while (sortedArray[j] > pivot) {
                j -= 1
            }

            if (i <= j) {
                val x = sortedArray[j]
                sortedArray[j] = sortedArray[i]
                sortedArray[i] = x
                i += 1
                j -= 1
            }
        }

        if (first < j) {
            sortedArray = quicksort(sortedArray, first, j)
        }

        if (last > i) {
            sortedArray = quicksort(sortedArray, i, last)
        }
        return sortedArray
    }