In standard Deterministic Quick Sort, we usually pick the first or last element as the Pivot. If the array is already sorted (e.g., [1, 2, 3, 4, 5]), picking the last element means we split the array into size $N-1$ and $0$ every single time, triggering the worst-case $O(N^2)$ time complexity.

Instead of deterministically picking the last element, we generate a random number between $1$ and $N$, and swap that random element with the last element. Then we proceed with standard partitioning. This guarantees that no specific input (like a sorted array) can force the worst-case scenario.

1Algorithm Randomized_QuickSort(A, p, r):
2   if p < r:
3      // Step 1: Find a random pivot and partition
4      q = Randomized_Partition(A, p, r)
5      
6      // Step 2: Recurse on left side
7      Randomized_QuickSort(A, p, q - 1)
8      
9      // Step 3: Recurse on right side
10      Randomized_QuickSort(A, q + 1, r)
11
12Algorithm Randomized_Partition(A, p, r):
13   i = Random(p, r)  // Pick a random index
14   Swap(A[i], A[r])  // Swap it to the end
15   return Partition(A, p, r) // Standard partition

Expected (Average) Case: Because the pivot is chosen uniformly at random, it will theoretically split the array roughly down the middle (like 25%-75% or 50%-50%) most of the time. This yields a recursion tree of height $\log N$, giving an expected time complexity of $O(N \log N)$.

Worst Case: If you are incredibly unlucky, the random number generator might pick the absolute largest element as the pivot every single time. The worst-case is technically still $O(N^2)$, but the probability of this happening on a large array is astronomically close to zero.