Quick Sort and Partition Logic

Partitioning creates the recursive contract

Quicksort partitions around a pivot, then sorts the partitions. Balanced partitions give expected O(n log n) time with suitable pivot selection; repeatedly extreme pivots can produce O(n²) time and deep recursion.

Copy codefun partition(values: IntArray, low: Int, high: Int): Int {
    val pivot = values[high]
    var boundary = low
    for (i in low until high) {
        if (values[i] < pivot) {
            val temp = values[i]; values[i] = values[boundary]; values[boundary] = temp
            boundary++
        }
    }
    val temp = values[boundary]; values[boundary] = values[high]; values[high] = temp
    return boundary
}

Call this only for a valid nonempty inclusive range. Afterward, values left of the returned position are smaller than the pivot, while those right are at least as large. Recursive calls must exclude the pivot index.

Exercise

Implement the recursive driver with a low >= high base case. Test already sorted, reverse-sorted, and all-equal inputs. Count partition imbalance before adding randomized pivot selection or a three-way partition.

Check: sorting in place does not eliminate recursion-stack space, and this partition is not stable.

Further reading: Quicksort