Quicksort is in place and runs on average in $\theta (n \log n)$, but has a worst-case running time of $\theta (n^2)$.

Method

The main logic in Quicksort is to divide and conquer.

const quicksort = (A, p, r) => {
	if(p >= r) return
	
	q = partition(A, p, r)
	quicksort(A, p, q - 1)
	quicksort(A, q + 1, r)

Divide the array by Partition method. Partition rearranges the subarray in place.

const partition = (A, p, r) => {
	let x = A[r] // pivot
	let i = p - 1
	for(let j = p; j < r; j++) {
		if(A[j] <= x) {
			i = i + 1
			[A[l], A[i]] = [A[i], A[l]]
		}
	[A[i+1], A[r]] = [A[r], A[i+1]]
	
	return i + 1
}