https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=287089
--- Comment #1 from Vivian Hussey <[email protected]> --- 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.
