Quick Sort

QuickSort involves two phases:

1. Partition: In the partition phase, all of the elements are reordered such that elements to the left of the pivot are less than the pivot, and right of the pivot greater than the pivot.

2. Sort: In the sort phase, the algorithm is applied down to the two groups recursively, until the entire array is sorted.

template <typename eType>
quickSort(vector<eTpye> &arr, int low, int high) {
    if (low < high) {
        auto pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high);
    }
}

template <typename eType>
int partition (vector<eTpye> &arr, int low, int high) {
    auto pivot = arr[high];  
    auto i = (low - 1);
    for (j = low; j <= high- 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high])
    return i + 1;
}