• 1 ≤ nums.length ≤ 5 * 10⁴
• -5 * 10⁴ ≤ nums[i] ≤ 5 * 10⁴
• Space Complexity: O(log N) for recursion stack
• Time Complexity: O(N log N) average

Quick Sort is a Divide and Conquer algorithm that centers around the concept of partitioning. The goal is to pick a "pivot" element and rearrange the array so that:
- Every element smaller than the pivot is moved to its left.
- Every element larger than the pivot is moved to its right.
- The pivot itself ends up in its final sorted position.

To perform this partitioning in-place (without extra memory), we use a two-pointer approach known as the Lomuto Partition Scheme:
1. Pivot Selection: We pick the last element of the range as the pivot.
2. The Explorer (j): This pointer scans every element from left to right.
3. The Boundary (i): This pointer keeps track of the "wall" between elements known to be smaller than the pivot and elements yet to be checked.

Whenever the Explorer finds a value smaller than the pivot, we swap it with the element at the Boundary and move the wall forward. Once the scan is complete, we swap the pivot into its correct spot at the wall.

Once the pivot is locked in place, the problem is reduced into two smaller, independent sub-problems:
1. Sort the subarray to the left of the pivot.
2. Sort the subarray to the right of the pivot.

We repeat this logic recursively until every subarray is reduced to a single element (the base case). Since every pivot was moved to its correct relative position, the entire array is now guaranteed to be sorted.

Quick Sort is often the default choice in programming language standard libraries (like Java's Arrays.sort or C++'s std::sort) because:
- Cache Efficiency: It has excellent locality of reference, meaning it accesses memory that is physically close together. This makes it much faster on modern hardware compared to Merge Sort.
- Minimal Memory: It is an in-place algorithm. It only needs O(log N) space for the recursion stack, whereas Merge Sort needs O(N) extra space to store temporary halves.
- Speed: In practice, its constant factors are smaller than Heap Sort or Merge Sort, making it faster for the average random array.

Avoid it when:
- You need a stable sort (where equal elements keep their original order).
- You are sorting Linked Lists (Merge Sort is superior here as it doesn't require random access).
- You are dealing with highly skewed data and cannot use a random pivot (risk of O(N^2)).

FUNCTION quicksort(arr, low, high):
    IF low < high:
        p = partition(arr, low, high)
        quicksort(arr, low, p - 1)
        quicksort(arr, p + 1, high)

FUNCTION partition(arr, low, high):
    pivot = arr[high]
    i = low
    FOR j from low to high-1:
        IF arr[j] < pivot:
            SWAP(arr[i], arr[j])
            i++
    SWAP(arr[i], arr[high])
    RETURN i

- Stability: No (partitioning involves long-distance swaps).
- In-Place: Yes (only uses O(log N) recursion stack).
- Time Complexity: O(N log N) average, O(N²) worst case.