# Program for Quicksort in Kotlin

In this article, we are going to learn how to implement Quicksort in Kotlin? Here you will find what is merge sort, its algorithm, and program in Kotlin.
Submitted by Aman Gautam, on December 17, 2017

Quicksort is a sorting algorithm which uses Divide and Conquer approach like Merge Sort. Its worst-case running time is O(n2), but best an average running time is O(n log (n) ). It is an in-place sorting.

Here is the three-step divide-and-conquer process for sorting a typical subarray A[p ..r].

Divide: Partition the array A[p..r] into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q+1..r]. Then Compute the index q as part of this partitioning procedure.

Conquer: Sort the two subarrays A[p..q-1] and A[q+1..r] by recursive calls to quicksort.

Combine: Because the subarrays are already sorted, no need to combine them, the entire array A[p ..r] is now sorted.

Algorithms

```    QUICK_SORT(A,p,r)
1.	if(p<r)
2.	q=partition(A,p,r)
3.	quick_sort(A,p,q-1)
4.	quick_sort(A,q+1,r)

PARTITION(A,p,r)
1.	x= A[r]
2.	I =p-1
3.	for j=p to r-1
4.	if A[j]<=x
5.	i=i +i
6.	exchange a[i] with a[j]
7.	exchange a[i+1] with a[r]
8.	return i+1
```

Algorithm source from Introduction to Algorithms by cormen

## Program to implement Quicksort in Kotlin

```fun quick_sort(A: Array<Int>, p: Int, r: Int) {
if (p < r) {
var q: Int = partition(A, p, r)
quick_sort(A, p, q - 1)
quick_sort(A, q + 1, r)

}
}

fun partition(A: Array<Int>, p: Int, r: Int): Int {
var x = A[r]
var i = p - 1
for (j in p until r) {
if (A[j] <= x) {
i++
exchange(A, i, j)
}
}
exchange(A, i + 1, r)
return i + 1
}

fun exchange(A: Array<Int>, i: Int, j: Int) {
var temp = A[i]
A[i] = A[j]
A[j] = temp
}

fun main(arg: Array<String>) {
print("Enter no. of elements :")

println("Enter elements : ")
var A = Array(n, { 0 })
for (i in 0 until n)

quick_sort(A, 0, A.size - 1)

println("Sorted array is : ")
for (i in 0 until n)
print("\${A[i]}  ")
}
```

Output

```Enter no. of elements :5
Enter elements :
10
34
22
56
74
Sorted array is :
10  22  34  56  74
```

Read more: Implementation of Quicksort in C++