Sort an Array Using Quicksort Algorithm

Statement#

Given an array of integers nums, sort it in ascending order using the quicksort algorithm.

Example#

Here’s an example of the quicksort algorithm:

Sample input#

[55, 23, 26, 2, 25]

Expected output#

[2, 23, 25, 26, 55]

Try it yourself#

Solution#

Here is an overview of how the quicksort algorithm works:

• Select a pivot element from the array to divide it into two parts.
  • We pick the first element as the pivot if we follow Hoare’s algorithm. Another common approach is to select a random element as the pivot.
• Reorder the array by comparing elements with the pivot element such that smaller values end up at the left side and larger values end up at the right side of the pivot.
• Now, the pivot element is in its correct sorted position.

By applying the above steps, we can recursively sort the sublists on the right and left sides of the pivot.

Let’s see a visual representation of the algorithm:

Time complexity#

The time complexity of this solution is linearithmic, $O(nlogn)$.

Space complexity#

The space complexity of this solution is logarithmic, $O(logn)$, because it consumes memory on the stack.