 # Quicksort

Quicksort is a unstable comparison sort algorithm with mediocre performance. Quicksort uses the partitioning method and can perform, at best and on average, at O(n log (n)). It can, however, perform at O(n2) in the worst case, making it a mediocre performing algorithm.

## Walkthrough

Quicksort is a divide and conquer recursive algorithm. The algorithm picks an index typically referred to as the pivot and divides the array into two sub-arrays above and below the pivot. Each sub-array is recursively passed into the `quickSort()` function.

### Partition

The `partition()` function does all of the work. This function requires 3 parameters: the original array, the starting index of the sub-array, and the end index of the sub-array. The `partition()` function follows these steps:

1. Set the `pivotValue` to equal the index of the array located at `(startIndex + endIndex) / 2`.
2. Starting from the `startIndex`, increment the `startIndex` forward until we find a value that is greater than the `pivotValue`.
3. Starting from the `endIndex`, decrement the `endIndex` backward until we find a value that is less than the `pivotValue`.
4. If the `startIndex` is greater than or equal to the `endIndex`, then return the `endIndex`.
5. If step 4 is not true, then swap the values at the `startIndex` and `endIndex` and restart the while-loop.