Quick sort is a divide and conquer algorithm that sorts an array.
The sorting algorithm partitions the input array around an arbitrary pivot.
This is achieved by maintaining pointers to elements on each side of the input array.
The 2 parts of the input array are recursively quick sorted.
Let's take the following input array
Aas an example
A = [3, 1, 8, 2, 9, 5]
Step through the images below to see how quick sort works
Before you look at the solution, try to code it yourself.
Time and Space Complexity
It takes logarithmic time to divide the problem into subprobems, 2 halves each time.
In every subproblem, we compare the pivot element with each element in the subarray, which takes linear time.
Therefore, the average time complexity of quick sort is
Comparing and swapping the pivot element in each iteration is done in place.
But since the implementation is recursive, the algorithm builds up the call stack for each sub problem. So the space complexity is