The Worst Case of Quicksort

Quicksort is one of the most efficient and commonly used sorting algorithms. It is a divide-and-conquer algorithm. It’s also an in-space algorithm as it does not use any extra space for sorting the input data, unlike the merge sort algorithm.

If you are a software engineer preparing for a tech interview, quicksort is one of the sorting algorithms you must be well-versed in. If you wish to learn quicksort in detail, check out our article on the Quicksort Algorithm. This post is dedicated to analyzing the “worst case” of quicksort. We’ll cover:

• What is the best and worst case of quicksort?
• When does the worst case of quicksort occur?
• FAQs related quicksort worst case

What Is the Best and Worst Case of Quicksort?

Before we get into the “when” and “why” of it, here are the best-case and worst-case scenarios of quicksort:

When Does the Worst Case of Quicksort Occur?

Quicksort works by dividing an array into smaller arrays and then sorting those smaller arrays. A pivot element is used to partition an array into smaller arrays; smaller arrays are divided recursively until an array with only one or no elements is created. Hence, the selection of the pivot element plays an important role in the efficiency of the quicksort algorithm.

But when the pivot element divides the array into two unbalanced sub-arrays (huge difference in size), the performance of quicksort decreases. Following are the cases where the pivot divides an array into two unbalanced sub-arrays:

• When the input array is already sorted, and we choose the leftmost element as the pivot element. In this case, we’ll have two extremely unbalanced arrays. One array will have 0 elements, and the other one will have N – 1 elements.

• When the given array is reverse sorted, and we choose the rightmost element as the pivot element. Again, in this case, the pivot elements will split the input array into two unbalanced arrays of size 0 and N – 1.

• When all the elements in the given array are the same. In such a scenario, the pivot element divides the array into one subarray of length N-1, and the time complexity of Quicksort increases significantly.

FAQs Related Quicksort Worst Case

Question 1: Can quicksort be implemented in O(NLogN) worst-case time complexity?

Answer: Yes, we can minimize the worst-case time complexity of quicksort to O(N*logN) by finding the median of the unsorted array in O(N) and using the median as the pivot. By doing this, we make sure that the array is divided into two subarrays of almost equal size, and we never encounter the case when the array is divided into subarrays of size 0 and N-1. But the constant factor of this method is very high, and therefore, it is not used in practice.

Question 2: Despite having a worst-case time complexity of O(N^2), why is quicksort considered a fast sorting algorithm?

Answer: The worst case of quicksort O(N^2) can be easily avoided with a high probability by choosing the right pivot. Obtaining an average-case behavior by choosing the right pivot element makes the performance better and as efficient as merge sort. Quicksort, in particular, exhibits good cache locality, which makes it faster than merge sort in many cases, such as in a virtual memory environment.

Want to Learn More About Sorting Algorithms?

Head to Interview Kickstart’s learn page for more articles on sorting, such as:

• Quicksort
• Merge sort
• Heap sort
• Bubble sort
• Selection sort
• Insertion sort
• Complexities of sorting algorithms
• And many more!

Looking for a Tech Interview Prep Coach?

Interview Kickstart offers the best technical interview prep courses that make you a better engineer and help you nail tech interviews.

As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

For more information on what it takes to prepare for and succeed at FAANG tech interviews, sign up for our free webinar.

——–

Article contributed by Abhinav Tiwari