How to Implement Quick Sort

Quick Sort picks one element as a pivot and rearranges the array so that all elements smaller than the pivot are on its left and all elements greater are on its right. The pivot is now in its final sorted position. Recursively apply the same process to the left and right sides.

The pivot can be the first element, the last element, the middle element, or a random element. Choosing the last element is the most common approach for learning. The choice of pivot affects performance but not correctness.

The Partition function rearranges elements around the pivot. Place the pivot at the end temporarily. Use a pointer i that starts just before the beginning of the segment. This pointer tracks the boundary between elements smaller than the pivot and elements larger than it.

Use a second pointer j to scan from the start to just before the pivot. If the element at j is smaller than or equal to the pivot, increment i and swap the elements at i and j. This moves the smaller element to the left side of the boundary.

After scanning all elements, swap the pivot with the element at index i plus one. The pivot is now in its correct sorted position. Everything to its left is smaller and everything to its right is larger. Return the pivot's final index.

Call Quick Sort recursively on the left segment from start to pivot index minus one. Call Quick Sort recursively on the right segment from pivot index plus one to end. These recursive calls keep partitioning until all segments have one or zero elements.

The base case is when the start index is greater than or equal to the end index, meaning the segment has one or zero elements. Simply return at that point. No further sorting is needed.