QuickSort.kt

    fun Array<Int>.quickSort() {
        quickSortImpl(this, 0, this.lastIndex)
    }

    fun quickSortImpl(input: Array<Int>, leftIndex: Int, rightIndex: Int) {
        if (input.size <= 1) return
        val pivotIndex = (leftIndex + rightIndex) / 2
        val pivotValue = input[pivotIndex]
        input[pivotIndex] = input[rightIndex]
        var j = leftIndex
        var i = leftIndex

        while (i < rightIndex) {
            if (input[i] < pivotValue) { // here we can swap < with > to change asc/desc
                val temp = input[i]
                input[i] = input[j]
                input[j] = temp
                j++
            }
            i++
        }

        input[rightIndex] = input[j]
        input[j] = pivotValue

        if (j - 1 > leftIndex) quickSortImpl(input, leftIndex, j - 1)
        if (j + 1 < rightIndex) quickSortImpl(input, j + 1, rightIndex)
    }

    @Test
    fun testQuicksort() {
        val tab = arrayOf(2, 5, 1, 3, 4, 0, 6, 2, 5)
        val tab2 = tab.clone()

        tab.sort()
        tab2.quickSort()

        assert(tab.contentEquals(tab2))

    }