Understanding Quick Sort

Quick Sort is an highly efficient, in-place sorting algorithm that also utilizes a Divide and Conquer strategy. It is one of the most widely used sorting algorithms due to its excellent practical performance.

How it works

1. Pivot Selection: Choose an element from the array to be the pivot (e.g., first, last, middle, or random element).
2. Partitioning: Rearrange the array so that all elements smaller than the pivot go to its left, and all elements larger than the pivot go to its right. After partitioning, the pivot is in its final sorted position.
3. Recursive Step: Recursively apply the above steps to the sub-array of smaller elements and the sub-array of larger elements.

Mathematical Complexities

• Best & Average Case Complexity O(N log N): Occurs when the pivot partition splits the array roughly in half at each step.
• Worst Case Complexity O(N²): Occurs when the pivot is consistently the smallest or largest element (e.g., sorting an already sorted array using the last element as pivot without randomization).
• Space Complexity O(log N): Requires space for the recursive call stack.

💡 Note: Quick Sort is typically faster in practice than Merge Sort because it operates in-place and has better cache locality. However, it is unstable and has an O(N²) worst-case performance if pivot selection is poor.