Quick Sort

QuickSort.kt

package ru.maksim.sample

import org.junit.jupiter.api.Test

class QuickSort {

    @Test
    fun sample() {
        val a = intArrayOf(3, 5, 2, 8, 6, 4)
        quickSort(a, 0, a.lastIndex)
    }

    private fun quickSort(a: IntArray, lo: Int, hi: Int) {
        if (hi > lo) {
            val p = partition(a, lo, hi)
            quickSort(a, lo, p - 1)
            quickSort(a, p + 1, hi)
        }
    }

    private fun partition(arr: IntArray, low: Int, high: Int): Int {
        // val pivotIndex = (low + high) / 2 // Choose midpoint as the pivot
        val pivotIndex = high
        val pivot = arr[pivotIndex]
        var i = low
        var j = high

        while (true) {
            while (arr[i] < pivot) {
                i++
            }
            while (arr[j] > pivot) {
                j--
            }
            if (i >= j) {
                return j // returning i would be incorrect for the input given
            }
            swap(arr, i, j)
            i++
            j--
        }
    }

    fun swap(arr: IntArray, i: Int, j: Int) {
        val temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
}