void merge(vector<int> &v, int s, int m, int e)
{
    vector<int> temp;

    int i, j;
    i = s;
    j = m + 1;

    while (i <= m && j <= e)
    {

        if (v[i] <= v[j])
        {
            temp.push_back(v[i]);
            ++i;
        }
        else
        {
            temp.push_back(v[j]);
            ++j;
        }
    }

    while (i <= m)
    {
        temp.push_back(v[i]);
        ++i;
    }

    while (j <= e)
    {
        temp.push_back(v[j]);
        ++j;
    }

    for (i = s; i <= e; ++i)
        v[i] = temp[i - s];
}

void mergeSort(vector<int> &A, int li, int ls)
{
    if (li < ls)
    {
        int mid = li + (ls - li) / 2;
        mergeSort(A, li, mid);
        mergeSort(A, mid + 1, ls);
        merge(A, li, mid, ls);
    }
}

void quickSort(vector<int> &A, int s, int e)
{
    int i, j, mid, piv;
    i = s;
    j = e;
    mid = s + (e - s) / 2;
    piv = A[mid];

    while (i < e || j > s)
    {
        while (A[i] < piv)
            i++;
        while (A[j] > piv)
            j--;

        if (i <= j)
        {
            swap(A[i], A[j]);
            i++;
            j--;
        }
        else
        {
            if (i < e)
                quickSort(A, i, e);
            if (j > s)
                quickSort(A, s, j);
            return;
        }
    }
}