quickSort

Hard · Recursion · 1 test cases

Implement the quicksort algorithm to sort an array of numbers in ascending order.

Examples

quickSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]) → [1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]

Starter code

function quickSort(arr) {

}

Complexity of the optimal solution

Time O(n log n) average, space O(n). Quicksort has an average time complexity of O(n log n). However, its worst-case performance (with a bad pivot choice on a sorted array) is O(n²). This implementation creates new arrays `left` and `right` at each step, leading to O(n) space complexity, which is higher than an in-place version.

Solve quickSort in the browser