QuickSort is a highly efficient, comparisonbased sorting algorithm that follows the divideandconquer strategy to sort an array or a list of elements. It was developed by Tony Hoare in 1960. The key idea behind QuickSort is to select a pivot element from the array, partition the other elements into two subarrays based on the pivot, and then recursively sort these subarrays.
Here’s a stepbystep explanation of the QuickSort algorithm:

 Choose a Pivot: Select an element from the array to serve as the pivot. The choice of pivot can affect the algorithm’s performance. In the basic implementation, the first element is often chosen as the pivot.
 Partitioning: Rearrange the elements in the array such that all elements less than the pivot are placed to its left, and all elements greater than the pivot are placed to its right. The pivot itself is in its final sorted position. This step is performed using a process called partitioning.
 Initialize two pointers, left and right, at the two ends of the array.
 Move the left pointer towards the right until an element greater than the pivot is found.
 Move the right pointer towards the left until an element less than the pivot is found.
 If left is still to the left of right, swap the elements at left and right.
 Repeat the above two steps until left is no longer to the left of right.
 Finally, swap the pivot element with the element at the right pointer.
 Recursion: After the partitioning step, the pivot is in its final sorted position. Recursively apply the QuickSort algorithm to the subarrays on the left and right of the pivot.
 Base Case: The recursion stops when the subarrays have one or zero elements, as they are already sorted by definition.
 Combine SubArrays: Since the pivot and subarrays are sorted, combining the left subarray, pivot, and right subarray will result in a fully sorted array.
Here’s a highlevel pseudocode of the QuickSort algorithm:
procedure quickSort(array) if length(array) <= 1 return array pivot = choosePivot(array) left = [] right = [] for element in array (excluding pivot) if element < pivot add element to left else add element to right sortedLeft = quickSort(left) sortedRight = quickSort(right) return concatenate(sortedLeft, pivot, sortedRight) end procedure
QuickSort has an averagecase time complexity of O(n log n), where n is the number of elements to be sorted. The worstcase time complexity is O(n^2), which occurs when the pivot selection consistently results in unbalanced partitions. However, in practice, QuickSort often outperforms other sorting algorithms due to its low constant factors and efficient cache utilization.
To improve QuickSort’s worstcase behavior, variations like Randomized QuickSort, which randomly select the pivot, and ThreeWay QuickSort, which handles duplicate elements efficiently, have been proposed.
PHP Implementation of Quick Sort
Follow this video for complete guidance :
function quickSort($array) { $length = count($array); if ($length <= 1) { return $array; } $pivot = $array[0]; $left = $right = array(); for ($i = 1; $i < $length; $i++) { if ($array[$i] < $pivot) { $left[] = $array[$i]; } else { $right[] = $array[$i]; } } return array_merge(quickSort($left), array($pivot), quickSort($right)); } $unsortedArray = array(7, 2, 1, 6, 8, 5, 3, 4); $sortedArray = quickSort($unsortedArray); echo "Unsorted Array: " . implode(", ", $unsortedArray) . "<br>"; echo "Sorted Array: " . implode(", ", $sortedArray);