void quicksort(int *arr, int p, int r)
{
    if (p >= r) return;

    int q = partition(arr, p, r);
    quicksort(arr, p, q);
    quicksort(arr, q+1, r);
}

int partition(int *arr, int p, int r)
{
    int pivotValue = arr[rand(p+(r-p)/2)];

    int i = p-1;
    int j = r+1;
    while (1)
    {
        do
        {
            j--;
        }
        while (arr[j] > pivotValue);

        do 
        { 
            i++;
        }
        while (arr[i] < pivotValue);

        if (i < j)
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        else
        {
            return j;
        }
    }
}

void mergesort(int *arr, int p, int r)
{
    if (p < r)
    {
        int q = p + (r-p)/2;
        mergesort(arr, p, q);
        mergesort(arr, q+1, r);
        merge(arr, p, q, r);
    }
}

void merge(int *arr, int p, int r)
{
    assert(p < r);

    int size = r-p+1;

    int *tmpArr = new int[size];

    int x = 0;
    int i = p;
    int j = q+1;
    while (i <= q && j <= r)
    {
        if (arr[i] < arr[j]) 
        {
            tmpArr[x] = arr[i];
            i++;
        }
        else
        {
            tmpArr[x] = arr[j-1];
            j++;
        }
        x++;
    }

    while (i <= q)  { tmpArr[x++] = arr[i++]; }
    while (j <= r)  { tmpArr[x++] = arr[j++]; }

    // copy back
    for (i = 0; i < size; i++) { arr[i+p] = tmpArr[i]; }

    delete [] tmpArr;
}