Sorting

Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

Basic Implementation

basic.kt 
fun partition(arr: IntArray, low: Int, high: Int): Int {
	val pivot = arr[high]
	var i = low - 1
	for (j in low until high) {
		if (arr[j] <= pivot) {
			i++
			val tmp = arr[i]
			arr[i] = arr[j]
			arr[j] = tmp
		}
	}
	val tmp = arr[i + 1]
	arr[i + 1] = arr[high]
	arr[high] = tmp
	return i + 1
}

fun quickSort(arr: IntArray, low: Int, high: Int) {
	if (low < high) {
		val pivotIndex = partition(arr, low, high)
		quickSort(arr, low, pivotIndex - 1)
		quickSort(arr, pivotIndex + 1, high)
	}
}

fun main() {
	val arr = intArrayOf(4, 1, 5, 2, 3)
	quickSort(arr, 0, arr.size - 1)
	println(arr.joinToString(prefix = "[", postfix = "]"))
}

The pinned first partition uses [4, 1, 5, 2, 3] with pivot 3. The diagrams track the boundary, swaps, and recursive ranges.

Step 1 - Choose the last value as pivot

The pivot is arr[4] = 3, and i starts just before the current range.

Initial partition state for [4, 1, 5, 2, 3].i0i1i2i3i441523j startspivot

Step 2 - Swap small values left

1 and 2 are <= pivot, so they move into the left partition.

After scanning values before the pivot: [1, 2, 5, 4, 3].i0i1i2i3i412543<= 3<= 3> 3> 3pivot

Step 3 - Place pivot, then recurse

Swapping pivot 3 into index 2 gives [1, 2, 3, 4, 5]; recurse on [1, 2] and [4, 5].

Pivot lands at index 2 and splits the remaining work.left rangepivotright range[1, 2]3 at i2[4, 5]quick_sort(0,1)fixedquick_sort(3,4)

Complexity

  • Time: O(n^2) worst, O(n log n) average
  • Space: O(log n) average call stack
  • Stable: no

Implementation notes

  • Kotlin stores the input as a primitive IntArray; val arr is not rebound, but quickSort mutates its slots in place.
  • quickSort(arr: IntArray, low: Int, high: Int) recurses only when low < high, then partitions and calls the left and right index ranges around pivotIndex.
  • partition(arr, low, high) chooses val pivot = arr[high] and tracks the left boundary with mutable var i = low - 1.
  • The Lomuto scan uses for (j in low until high). if (arr[j] <= pivot) uses Int comparison and moves equal values to the left side of the pivot.
  • Swaps use an explicit temporary variable: val tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp, and the pivot swap uses the same pattern with i + 1 and high.
  • No new list or array is allocated during sorting; the extra state is scalar indexes, pivot values, temp variables, and recursive stack frames.
  • The trace shows pivot 3: 4 stays right, 1 swaps left to [1, 4, 5, 2, 3], 5 stays right, 2 swaps left to [1, 2, 5, 4, 3], then pivot 3 moves to index 2 as [1, 2, 3, 4, 5].
  • println(arr.joinToString(prefix = "[", postfix = "]")) formats the mutated array as [1, 2, 3, 4, 5].
pivot The final element is moved to the boundary between smaller and larger values.
partition One scan rearranges the current range before the recursive calls.