How to construct an array to make qsort() having n^2 time complexity?

I heard a long time ago that the implementation of the qsort function is the quick sorting algorithm and has a worst-case time complexity of n^2.

But recently when I was trying to construct a set of data that would allow the qsort function to time out, I discovered that its implementation is not exactly the same as the widely known quick sort algorithm, and that it uses many optimisation tricks.

For example, there is a comment in the glibc implementation

/* Select median value from among LO, MID, and HI. Rearrange
LO and HI so the three values are sorted. This lowers the
probability of picking a pathological pivot value and
skips a comparison for both the LEFT_PTR and RIGHT_PTR in
the while loops. */

So how to construct an array to make qsort() having n^2 time complexity? Although I have read the source code of qsort in glibc, I still can’t come up with a constructor method.

I’ve tried ascending, descending and half up half down arrays, but none of these constructors work.

for (int i = 0; i < N / 2; i++)
{
    a[i] = i;
}
for (int i = N / 2; i < N; i++)
{
    a[i] = N - 1 - i;
}

and this

for (int i = 0; i < N; i++)
{
    if (i & 1)
        a[N - 1 - i / 2] = i;
    else
        a[i / 2] = i;
}

You need to sign in to view this answers