﻿==================================================
2. QUICK SORT (LAST ELEMENT AS PIVOT)
==================================================

ALGORITHM:
1. Select the last element A[high] as pivot.
2. Initialize i = low - 1.
3. Traverse the array using j = low to high - 1.
4. If A[j] <= pivot, increment i and swap A[i] with A[j].
5. Swap A[i+1] with the pivot.
6. Return the pivot index.
7. Recursively sort the left and right partitions.

RECURRENCE RELATION:
Best Case:
T(n) = 2T(n/2) + O(n)

Worst Case:
T(n) = T(n-1) + O(n)

RECURSIVE ANALYSIS:
Best Case:
T(n) = O(n log n)

Worst Case:
T(n) = n + (n-1) + (n-2) + ... + 1
T(n) = O(n^2)

TIME COMPLEXITY:
Best Case    : O(n log n)
Average Case : O(n log n)
Worst Case   : O(n^2)
Space        : O(log n) average, O(n) worst