Quick Sort

Category: Sorting

Difficulty: Hard

Description

Write a function that takes in an array of integers and returns a sorted version of that array. Use the Quick Sort algorithm to sort the array.

If you're unfamiliar with Quick Sort, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

Sample Input

array = [8, 5, 2, 9, 5, 6, 3]

Sample Output

[2, 3, 5, 5, 6, 8, 9]

Optimal Space & Time Complexity

Best: O(nlog(n)) time | O(log(n)) space - where n is the length of the input array\nAverage: O(nlog(n)) time | O(log(n)) space - where n is the length of the input array\nWorst: O(n^2) time | O(log(n)) space - where n is the length of the input array