Sorting

Quick Sort (Lomuto)

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

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Kotlin DSA implementation can be compared directly with the other languages.

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.

Visual walkthrough

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)

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 = "]"))
}

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].