Kotlin Program to Implement Quick Sort Algorithm

A Kotlin program for quick sort uses a quickSort function that picks a pivot, partitions the list, and recursively sorts sublists; for example: fun quickSort(arr: MutableList, low: Int, high: Int) { if (low < high) { val pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high) } }.

Examples

Input[3, 1, 4, 1, 5]

Output[1, 1, 3, 4, 5]

Input[10, 7, 8, 9, 1, 5]

Output[1, 5, 7, 8, 9, 10]

Input[]

Output[]

How to Think About It

To sort a list using quick sort, first choose a pivot element. Then rearrange the list so that all smaller elements come before the pivot and all larger come after. Repeat this process on the smaller parts until the whole list is sorted.

Algorithm

1

Choose the last element as pivot.

2

Partition the list so elements less than pivot are left, greater are right.

3

Recursively apply quick sort to the left sublist.

4

Recursively apply quick sort to the right sublist.

5

Stop when sublist has zero or one element.

Code

kotlin

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

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

fun main() {
    val list = mutableListOf(10, 7, 8, 9, 1, 5)
    quickSort(list, 0, list.size - 1)
    println(list)
}

Output

[1, 5, 7, 8, 9, 10]

Dry Run

Let's trace sorting [10, 7, 8, 9, 1, 5] through the quick sort code.

1

Initial call

quickSort called with low=0, high=5, array=[10, 7, 8, 9, 1, 5]

2

Partitioning

Pivot=5, rearranged array after partition: [1, 5, 8, 9, 10, 7], pivot index=1

3

Left recursive call

quickSort called with low=0, high=0 (single element), returns immediately

4

Right recursive call

quickSort called with low=2, high=5, array=[8, 9, 10, 7]

5

Partitioning right sublist

Pivot=7, rearranged array: [1, 5, 7, 9, 10, 8], pivot index=2

6

Further recursive calls

Sort left sublist low=2, high=1 (empty), right sublist low=3, high=5

7

Final sorting

After sorting right sublist, final array: [1, 5, 7, 8, 9, 10]

Step	Array State	Pivot	Pivot Index
1	[10, 7, 8, 9, 1, 5]	5	1
2	[1, 5, 8, 9, 10, 7]	7	2
3	[1, 5, 7, 9, 10, 8]	8	5
4	[1, 5, 7, 8, 9, 10]	-	-

Why This Works

Step 1: Choosing a pivot

The pivot divides the list into smaller and larger parts using partition.

Step 2: Partitioning the list

Elements less than or equal to pivot move left; others move right, so pivot is in correct place.

Step 3: Recursive sorting

Quick sort repeats on left and right parts until all parts are sorted, resulting in a sorted list.

Alternative Approaches

Using Lomuto partition scheme

kotlin

fun lomutoPartition(arr: MutableList<Int>, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low
    for (j in low until high) {
        if (arr[j] < pivot) {
            arr[i] = arr[j].also { arr[j] = arr[i] }
            i++
        }
    }
    arr[i] = arr[high].also { arr[high] = arr[i] }
    return i
}

fun quickSortLomuto(arr: MutableList<Int>, low: Int, high: Int) {
    if (low < high) {
        val pi = lomutoPartition(arr, low, high)
        quickSortLomuto(arr, low, pi - 1)
        quickSortLomuto(arr, pi + 1, high)
    }
}

Lomuto is simpler but can be less efficient on some inputs compared to Hoare partition.

Using built-in sort with custom comparator

kotlin

fun quickSortBuiltIn(arr: MutableList<Int>) {
    arr.sort()
}

This uses Kotlin's built-in sort which is optimized but does not teach quick sort logic.

Complexity: O(n log n) average, O(n^2) worst case time, O(log n) due to recursion stack space

Time Complexity

Quick sort divides the list and sorts sublists recursively, averaging O(n log n) because each partition splits the list roughly in half.

Space Complexity

It uses O(log n) space for recursion calls; the sorting is done in-place without extra arrays.

Which Approach is Fastest?

Quick sort is generally faster than simple sorts like bubble sort; built-in sorts may use hybrid algorithms optimized for real data.

Approach	Time	Space	Best For
Quick Sort (Hoare)	O(n log n) avg	O(log n)	General-purpose in-place sorting
Quick Sort (Lomuto)	O(n log n) avg	O(log n)	Simpler code, less efficient on some inputs
Built-in sort	O(n log n) avg	O(n)	Best performance, no learning quick sort logic