Quicksort Algorithm Explained [With Example]

Quick Sort is based on the concept of Divide and Conquer algorithm, which is also the concept used in Merge Sort. The difference is, that in quick sort the most important or significant work is done while partitioning (or dividing) the array into subarrays, while in case of merge sort, all the major work happens during merging the subarrays. For quick sort, the combining step is insignificant.

Top Machine Learning Courses & AI Courses Online

Quick Sort is also called partition-exchange sort. This algorithm divides the given array of numbers into three main parts:

  1. Elements less than the pivot element
  2. Pivot element
  3. Elements greater than the pivot element

Pivot element can be chosen from the given numbers in many different ways:

  1. Choosing the first element
  2. Choosing the last element (example shown)
  3. Choosing any random element
  4. Choosing the median

For example: In the array {51, 36, 62, 13, 16, 7, 5, 24}, we take 24 as pivot (last element). So after the first pass, the list will be changed like this.

{5 7 16 13 24 62 36 51}

Trending Machine Learning Skills

Enrol for the Machine Learning Course from the World’s top Universities. Earn Masters, Executive PGP, or Advanced Certificate Programs to fast-track your career.

Hence after the first pass, the array is sorted such that all elements less than the chosen pivot are on its left side and all greater elements on its right side. The pivot is finally at the position it is supposed to be in the sorted version of the array. Now the subarrays {5 7 16 13} and {62 36 51} are considered as two separate arrays, and same recursive logic will be applied on them, and we will keep doing this until the complete array is sorted.

Also Read: Heap Sort in Data Structure

How does it work?

These are the steps followed in the quick sort algorithm:

  1. We choose our pivot as the last element, and we start to partition (or divide) the array for the first time.
  2. In this partitioning algorithm, the array is broken into 2 subarrays such that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it.
  3. And the pivot element will be at its final sorted position.
  4. The elements in the left and right subarrays do not have to be sorted.
  5. Then we recursively pick the left and right subarrays, and we perform partitioning on each of them by choosing a pivot in the subarrays and the steps are repeated for the same.

Shown below is how the algorithm works in C++ code, using an example array.

void QuickSort(int a[], int low, int high)




int p= partition(a,low,high);





int partition(int a[], int low, int high)


int pivot=a[high];

int i=low;

for(int j=low; j<high; j++)









return i;


int main()


int arr[]={6,1,5,2,4,3};


cout<<”The sorted array is: “;

for(int i=0; i<6; i++)

cout<<arr[i]<<” “;

return 0;


Below is a pictorial representation of how quick sort will sort the given array.

Suppose the initial input array is:

So after our first partition, the pivot element is at its correct place in the sorted array, with all its smaller elements to the left and greater to the right.

Now QuickSort() will be called recursively for the subarrays {1,2} and {6,4,5} and continue till the array is sorted.

Must Read: Types of AI Algorithms You Should Know

Complexity Analysis

Best Case Time Complexity: Ω(n*log n)

Average Time Complexity: Θ(n*log n)

Worst Case Time Complexity: O(n2)

If partitioning leads to nearly equal subarrays, then the running time is the best, with time complexity as O(n*log n).

Worst case happens for arrays with cases where the elements are already sorted, and pivot is chosen as the last element. Here the partitioning gives unbalanced subarrays, where all elements are already smaller than the pivot and hence on its left side, and no elements on the right side.

Space Complexity (considering recursion stack): O(n*log n) 

Popular AI and ML Blogs & Free Courses


Quicksort is a comparison-based algorithm and it is not stable. A small optimization that can be done, is to call the recursive QuickSort() function for the smaller subarray first and then the larger subarray.

Overall, Quick Sort is a highly efficient sorting technique that can give better performance than Merge Sort in the case of smaller arrays. 

If you are keen on learning more, check out upGrad & IIIT-B’s PG Diploma in Machine Learning and AI Program.

What are the disadvantages of using the quicksort algorithm?

In general, the quick sort algorithm is the most efficient and extensively used technique for sorting a list of any size, although it does have some disadvantages. It's a fragile method, which implies that if a minor flaw in the implementation goes unchecked, the results will suffer. The implementation is difficult, especially if recursion is not available. One little limitation of the quick sort algorithm is that its worst-case performance is comparable to the bubble, insertion, or select sorts' typical performances.

What is the bucket sort algorithm used for?

The bucket sort algorithm is a sorting method that is used to put different elements into different groups. It is so named because the various subgroups are referred to as buckets. Due to the sheer uniform distribution of elements, it is asymptotically fast. However, if we have a huge array, it is ineffective since it raises the cost of the total process, making it less affordable.

Which one is better to use—the quicksort or the mergesort algorithm?

For tiny data sets, Quicksort is quicker than other sorting algorithms like Selection Sort, but Mergesort has consistent performance regardless of data size. Quicksort, on the other hand, is less efficient than mergesort when dealing with bigger arrays. Mergesort takes up more space, but quicksort takes up very little. Quicksort, in particular, has strong cache locality, making it quicker than merge sort in many situations, such as in a virtual memory environment. As a result, quicksort outperforms the mergesort algorithm.

Want to share this article?

Lead the AI Driven Technological Revolution

Learn More

Leave a comment

Your email address will not be published. Required fields are marked *

Our Popular Machine Learning Course

Get Free Consultation

Leave a comment

Your email address will not be published. Required fields are marked *

Get Free career counselling from upGrad experts!
Book a session with an industry professional today!
No Thanks
Let's do it
Get Free career counselling from upGrad experts!
Book a Session with an industry professional today!
Let's do it
No Thanks