[Bug 287089] [libc] qsort insertion sorts all pre-partitioned arrays, allowing trivial n^2 inputs

https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=287089

--- Comment #1 from Vivian Hussey <raspberryvivigrette@gmail.com> ---
As proof that this doesn't just affect the reversed case, we can randomize each
half of the array skipping the ninther points and it will still get roughly
O(n^2), with an average case of O(n^2/8) comparisons.

On my Pixel 6a:

qsort: 1251184276 compares, 9.468854 seconds
qsort: 1251317849 compares, 9.534520 seconds
qsort: 1246502732 compares, 9.495409 seconds


#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define N 100000
static size_t ncmp = 0;
static int buf[N];
static const int ninther_idxes[9] = {
    0, N / 8, 2 * N / 8, 3 * N / 8, N / 2, 5 * N / 8, 6 * N / 8, 7 * N / 8, N -
1
};

static int icmp(const void *a, const void *b)
{
    int x = *(const int *)a;
    int y = *(const int *)b;
    ++ncmp;
    return (x > y) - (x < y);
}

// Shuffle a subarray without touching the ninthers
static void shuffle(int *arr, int low, int n)
{
    while (n-- > low + 2) {
        if (bsearch(&n, ninther_idxes, 9, sizeof(int), icmp)) {
            continue;
        }
        int idx = -1;

        do {
            idx = rand() % (n - low) + low;
        } while (bsearch(&idx, ninther_idxes, 9, sizeof(int), icmp));

        int tmp = arr[idx];
        arr[idx] = arr[n];
        arr[n] = tmp;
    }
}


int main()
{
    srand(time(0));
    // Start with a sorted array
    for (size_t i = 0; i < N; i++) {
        buf[i] = i;
    }
    // Shuffle each half, skipping the ninther points
    shuffle(buf, 0, N / 2 - 1);
    shuffle(buf, N / 2, N);
    ncmp = 0;
    // The array is already partitioned, so qsort will blindly start insertion
sorting it
    // due to the "swap_cnt" check
    double start = clock();
    qsort(buf, N, sizeof(int), icmp);
    double end = clock();
    printf("qsort: %zu compares, %lf seconds\n", ncmp, (end - start) /
CLOCKS_PER_SEC);
}

-- 
You are receiving this mail because:
You are the assignee for the bug.