Summary

Random pivot selection makes the expected split independent of input order. A Lomuto partition places the pivot and recursively sorts the two sides.

How it Works

• Choose an index uniformly at random in the current range.

• Move that value to the end and partition smaller values before it.

• Recurse on both sides of the pivot.