Quicksort is a popular and efficient sorting algorithm, often utilized due to its average-case time complexity of $O(n \log n)$. However, a common point of confusion revolves around whether Quicksort is an in-place sorting algorithm or not.

Understanding In-Place Algorithms

An in-place algorithm requires a small, constant amount of extra space to transform input data, typically $O(1)$ space complexity. This usually means the algorithm doesn't depend on the input size for extra space allocation.

Quicksort: Basic Mechanism

Quicksort 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. This partitioning process is crucial for understanding whether Quicksort is in-place:

1. Partitioning: This is done in such a way that it reorders the elements around the pivot. Two pointers usually achieve this: one starting from the beginning and another from the end, both converging towards the pivot.
2. Recursive sorting: After partitioning, Quicksort recursively sorts the sub-arrays on either side of the pivot.

Is Quicksort In-Place?

Argument for In-Place

Quicksort is often classified as an in-place algorithm by convention because:

• Space Complexity: Classical implementations of Quicksort such as Lomuto's and Hoare's partition schemes manage the partitioning step entirely within the original data structure, employing only a handful of variables. Thus, the additional space usage is $O(\log n)$, due largely to the stack space consumed by recursive calls.
• No Extra Data Structure: During partitioning, no additional arrays or significant data structures are created to hold parts of the array components.

Argument Against In-Place

Though Quicksort is typically considered in-place, it doesn't strictly adhere to the definition in every context:

• Recursive Stack Usage: The recursion depth can go up to $O(n)$ in the worst case, especially if the pivot choices are made poorly, like choosing the first or last elements in a sorted array. This use of the call stack implies that memory usage can be larger than typical in-place algorithms.
• Alternative Implementations: Some non-conventional implementations of Quicksort utilize additional data structures for the sake of optimization or clarity, which may not qualify as in-place.

Examples and Illustrations

Classic In-Place Partitioning

Here's a step-by-step illustration using the Hoare partition scheme: