24. Quick Sort: Partitioning and Recursion (Part 2)

The Lomuto Partition Scheme (Simplified)

1. Select the last element as the pivot.
2. Use an index i (starting at the first element) to track where the 'smaller' boundary ends.
3. Iterate through the array j:
   • If arr[j] is less than or equal to the pivot, swap arr[i] and arr[j], and increment i.
4. Finally, swap the pivot into position i.

Efficiency Analysis

• Average Case Time: O(N log N). This is highly efficient and typically faster in practice than Merge Sort due to better constant factors (it uses fewer memory accesses).
• Worst Case Time: O(N²).
  • This happens if the pivot selection is consistently poor (e.g., always choosing the smallest or largest element), leading to unbalanced partitions (one sub-array of size N-1 and one of size 0). This is rare with good pivot selection strategies (like median-of-three or randomized pivot).