void insert_sort(double* a, int n) {
    int i, j; double tmp;
    for (i = 1; i < n; ++i) {
        tmp = a[i];
        for (j = i; j > 0; --j) {
            if (a[j - 1] <= tmp)
                break;
            a[j] = a[j - 1];
        }
        a[j] = tmp;
    }
}

int partition(double* a, int n, int (*p)(double, double)) {
    double x; int i = -1, j = n;
    swap(a, a + n / 2);
    x = a[0];
    while (1) {
        do --j;
        while ((*p)(a[j], x) < 0);
        do ++i;
        while ((*p)(a[i], x) > 0);
        if (i < j)
            swap(a + i, a + j);
        else return j;
    }
}

void quicksort(double* a, int n, int (*p)(double, double)) {
    int k;
    double *t;
    if (n < 1) return;
    while (n > 1) {
        k = partition(a, n, p);
        if (k + 1 < n - k - 1) {
            ++k;
            n -= k;
            t = a;
            a += k;
        }
        else  {
        t = a + k + 1;
        k = n - k - 1;
        n -= k;
        }
        quicksort(t, k, p);
    }
}