# Quick sort

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

`A`

as an exampleA = [3, 1, 8, 2, 9, 5]

Step through the images below to see how

*quick sort*works## Try it

Before you look at the solution, try to code it yourself.

## Solution

### 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

`O(n*log n)`

.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`O(log n)`

.## 5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.

- 1.Merge intervalsMedium
- 2.Kth largest in arrayMedium
- 3.Intersection of ArraysMedium
- 4.Search sorted matrixHard
- 5.Search row & col sorted matrixHard