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 example

A = [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.

def quick_sort(arr: list[int]) -> list[int]:
    # implement quick_sort
    return arr

1def quick_sort(arr: list[int]) -> list[int]:
2    # implement quick_sort
3    return arr
4

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).

Master Sorting & Searching by trying the coding challenges below.

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.