``package algorithmdesignmanualbook.sortingimport utils.shouldBe/** * NO need to sort all the items. * Just find the sort the items before the median index * Using quicksort, find the partition. * Then throw away the left partition if the median index lies in the right portion * while calibrating the new median index. * * Similar to finding the kth smallest item in the unsorted list */private fun fastMedian(array: IntArray, low: Int, high: Int, medianIndex: Int): Int {    val j = partition(array, low, high)    return if (j - low == medianIndex) {        array[j]    } else if (j - low > medianIndex) {        fastMedian(array, low, j - 1, medianIndex)    } else {        fastMedian(array, j + 1, high, medianIndex - j - 1 + low)    }}private fun quickSort(array: IntArray, low: Int, high: Int) {    if (low < high) {        val j = partition(array, low, high)        quickSort(array, low, j)        quickSort(array, j + 1, high)    }}private fun partition(array: IntArray, low: Int, high: Int): Int {    fun swap(index1: Int, index2: Int) {        val temp = array[index1]        array[index1] = array[index2]        array[index2] = temp    }    val pivot = array[low]    var i = low    var j = high    do {        while (array[i] <= pivot) i++        while (array[j] > pivot) j--        if (i < j) swap(i, j)    } while (i < j)    swap(low, j)    return j}fun midpointIndex(array: IntArray): Int {    return (array.size / 2)}fun main() {    run {        val original = intArrayOf(9, 1, 0, 2, 3, 4, 6, 8, 7, 10, 5)        val expected = original.sorted().toIntArray()        val quickSortInput = original.clone()        quickSort(quickSortInput, 0, original.lastIndex)        quickSortInput shouldBe expected        fastMedian(original, 0, original.lastIndex, midpointIndex(original)) shouldBe 5    }    run {        val original = intArrayOf(-90, 11, 30, 44, 20, 12, 22, -10, 1, 8, 90, 7, 10)        fastMedian(original, 0, original.lastIndex, midpointIndex(original)) shouldBe 11    }}``