After talking about Insertion sort and Heap sort, another important sorting algorithm is quick sort. It is pretty simple algorithm, and will be easy to understand using an example. Lets say we have this random array which we are trying to sort

9, 5, 7, 1, 2, 4, 3, 8, 6

Most critical step of quick sort is to select a pivot element from the array. There are multiple approaches to select the pivot like- first element, last element, mid element, random element, mean, median etc. For sake of simplicity, lets say we randomly select the pivot as 5 for first iteration. Once pivot is selected, the array is divided into 2 arrays, one with elements smaller than pivot and other greater

Iteration 1:

A1: 1, 2, 4, 3

P: 5

A2: 9, 7, 8, 6

In next iteration, one of the arrays (A1) is chosen and again a pivot (say 3) is selected. The same exercise is repeated of breaking down the array into 2 sub arrays unless we get an array of size 1. After that the arrays are merged recursively in same order as they were created, ending up into final sorted array.

Average & Best Case: If we take above case where we kept on dividing the problem array into half (N/2 then N/4, N/8 and so on), and hence halfing number of comparison in every next step. we are looking at a complexity of N Log N.

Worst Case: In worst case, lets say we select highest element every time. So instead of having half the elements in an array, we have N-1 elements in next step. So in this case we end up N*N (N Square) complexity