| 9 | 36 | 39 | 46 | 4 | 2 | 45 | 13 |
| i | j |
Quicksort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. It is an algorithm that is based on the divide-and-conquer technique and is one of the fastest and efficient sorting algorithms in practical scenarios. Unlike merge sort, which divides its input’s element according to their position in the array, quicksort divides the elements according to their value. The quicksort sorting algorithm is an in place sorting algorithm, requiring small additional amounts of memory to perform the sorting.
Quicksort rearranges elements of a given array A[0..n-1] to achieve its partition. Partition is a situation where all the elements before some position s are smaller than or equal to A[s] (the so-called pivot) and all elements after position s are greater than or equal to A[s].
Obviously, after a partition has been achieved, A[s] will be in its final position in the sorted array, and we can continue sorting the two sub-arrays of the elements preceding and following A[s] independently.