Interview Kickstart has enabled over 3500 engineers to uplevel.
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:
Before we get into the “when” and “why” of it, here are the best-case and worst-case scenarios of quicksort:
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:
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.
Head to Interview Kickstart’s learn page for more articles on sorting, such as:
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!
Article contributed by Abhinav Tiwari