How does the quicksort algorithm sort an array?

Quicksort algorithm sorts an array by dividing it into two smaller arrays around a pivot element and recursively sorting them.

Quicksort, also known as partition-exchange sort, is a highly efficient sorting algorithm that employs the divide-and-conquer strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

The first step in the quicksort algorithm is to choose a pivot. This could be the first element, the last element, the median, or any random element of the array. The choice of pivot does not change the correctness of the algorithm, but it can significantly affect its efficiency. A common strategy is to pick the last element of the array as the pivot.

Next, the algorithm partitions the array. It starts with two pointers, one at the beginning of the array and one at the end. The algorithm moves the pointers towards each other until they find an element on the wrong side of the pivot. These elements are then swapped. This process continues until the pointers meet, at which point the pivot is swapped with the element pointed to by the pointers. This ensures that the pivot is in its final sorted position and that all elements to its left are smaller and all elements to its right are larger.

The algorithm then recursively applies the same process to the sub-arrays formed by the elements to the left and right of the pivot. This is done until the base case is reached, which is when the sub-array to be sorted has only one element or no elements at all.

Quicksort is an in-place sorting algorithm, meaning it sorts the array by making changes directly to it, without needing to create a new array. This makes it space-efficient. However, its worst-case time complexity is O(n^2), which occurs when the array is already sorted or reverse sorted. Despite this, quicksort is often faster in practice than other O(n log n) algorithms, such as mergesort or heapsort, because its inner loop can be efficiently implemented on most architectures.