Describe how QuickSort works.?

Quicksort is a widely used sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. It is a comparison sort and, in efficient implementations, is not a stable sort. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.

The basic idea behind quicksort is to:

1. Choose a “pivot” element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The pivot element is then in its final position.

2. This is done recursively, where we sort the sub-arrays in a similar manner, until the base case is reached (arrays of size zero or one are already sorted).

The steps to implement QuickSort are as follows:

1. Choose an element in the array as the pivot. The choice of pivot can vary - it could be the first element, the last element, a random element, or the median. Different pivot-picking strategies can affect the complexity.

2. Partition the array into two segments. In the first segment, all elements are less than or equal to the pivot and in the second segment, all elements are greater than the pivot. This step is the key to QuickSort and is performed using a method called "Partitioning".

3. Recursively implement QuickSort on the two segments.

The pseudo-code implementation of quicksort is:

function quicksort(array)
   if length(array) <= 1
      return array
   select and remove a pivot value 'pivot' from array
   create empty lists 'less' and 'greater'
   for each x in array
      if x <= pivot then append x to 'less'
      else append x to 'greater'
   return concatenate(quicksort(less), pivot, quicksort(greater))

The partition step is very crucial and can be done in the following way:

function partition(array, low, high)
   pivot = array[high]
   i = (low - 1)
   for j = low to high-1
      if array[j] < pivot
         i++
         swap array[i] and array[j]
   swap array[i + 1] and array[high]
   return (i + 1)

In mathematical notation, the worst-case time complexity of QuickSort is O(n²) and the best-case and average-case time complexity is O(n log n), where n is the number of elements in the array to be sorted. In practice, QuickSort often outperforms other sorting algorithms for larger datasets.