Quicksort

Quicksort is another highly efficient, divide-and-conquer sorting algorithm. It's often faster in practice than other O(n log n) algorithms like Merge Sort, primarily due to better cache performance and being an in-place sort (using only O(log n) stack space for recursion). The algorithm works as follows: 1. **Partition**: Pick an element from the array, called a 'pivot'. Rearrange the array so that all elements smaller than the pivot come before it, while all elements greater come after it. After this partitioning, the pivot is in its final sorted position. 2. **Conquer**: Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values. The performance of Quicksort is highly dependent on the choice of the pivot. If the pivot selection consistently divides the array into roughly equal halves, the complexity is O(n log n). However, if the pivot is consistently the smallest or largest element (e.g., in an already sorted array with the last element chosen as pivot), the partitions are highly unbalanced, leading to a worst-case time complexity of O(n^2). To mitigate this, strategies like picking a random pivot or using the 'median-of-three' are employed. Despite its worst-case potential, Quicksort's average-case performance is excellent, making it a widely used algorithm.