void quickSort2(int a[], int first, int last) {
    if (first < last) {
        int pivotIndex = partition(a, first, last); // giai thich cai ham lam gi 

        quickSort2(a, first, pivotIndex - 1);
        quickSort2(a, pivotIndex + 1, last);

    }
}
                     int sortFirstMiddleLast(int a[], int first, int last) {
    int mid = first + (last - first) / 2;
    if (a[first] > a[mid])
        swap(a[first], a[mid]);
    if (a[mid] > a[last])
        swap(a[mid], a[last]);
    if (a[first] > a[mid])
        swap(a[first], a[mid]);

    return mid;
   
}
int partition(int a[], int first, int last) {
    int pivotIndex, pivot, indexFromLeft, indexFromRight;
  
    pivotIndex = sortFirstMiddleLast(a, first, last);
    swap(a[pivotIndex], a[last - 1]);

    pivotIndex = last - 1;
    pivot = a[pivotIndex];
    indexFromLeft = first + 1;
    indexFromRight = last - 2;

    bool done = false;

    while (!done) {
        while (a[indexFromLeft] < pivot)
            indexFromLeft += 1;
        while (a[indexFromRight] > pivot)
            indexFromRight -= 1;

        if (indexFromLeft < indexFromRight) {
            //?
            swap(a[indexFromLeft], a[indexFromRight]);
            indexFromLeft += 1;
            indexFromRight -= 1;
        }
        else
            done = true;
    }

    swap(a[pivotIndex], a[indexFromLeft]);
    pivotIndex = indexFromLeft;
    return pivotIndex;

 
}