Summary

Quick Sort is a highly efficient sorting algorithm based on the Divide and Conquer paradigm. It works by selecting an element from the array, called the pivot, and rearranging the other elements in a process called partitioning. After partitioning, the pivot is in its final sorted position. This process is then applied recursively to the sub-arrays of elements smaller and larger than the pivot.

How it Works

• 1. Choose a Pivot: An element is chosen from the array to be the pivot. Common strategies include picking the first, last, a random element, or the median of three. This implementation uses the last element of the current sub-array as the pivot.

• 2. Partition: The array is reordered so that all elements with values less than the pivot come before it, while all elements with values greater than the pivot come after it. After this step, the pivot is in its final sorted position. This implementation uses the Lomuto partition scheme.

• 3. Recurse: The Quick Sort algorithm is recursively called on the two sub-arrays: the one with elements smaller than the pivot, and the one with elements larger than the pivot.

• 4. Base Case: The recursion stops when a sub-array has zero or one element, as it is already considered sorted.