idea
Not stable. Can be more performant than merge sort.
Between $O(n^2)$ and $O(n \times log(n))$
links
references
https://en.wikipedia.org/wiki/Quicksort
https://www.geeksforgeeks.org/quick-sort/?ref=lbp
Reference implementation
function quickSortRec(array, low, high) {
if (high <= low) {
return
}
const pivot = partition(array, low, high)
quickSortRec(array, low, pivot - 1)
quickSortRec(array, pivot + 1, high)
}
function partition(array, low, high) {
const pivot = array[high]
let i = low - 1
for (let j = low; j < high; j++) {
if (array[j] < pivot) {
i++
swap(array, i, j)
}
}
swap(array, i + 1, high)
return i + 1
}
function swap(array, i, j) {
const tmp = array[i]
array[i] = array[j]
array[j] = tmp
}
function quickSort(array) {
quickSortRec(array, 0, array.length - 1)
}
const array = [3, 4, 1, 9, 0, 2, 7, 33, 11]
quickSort(array)
console.log(array)