qsort madness

qsort() (redhat glibc 2.3.2-95.30) attempts to be clever with memory by switching to a different algorithm for large inputs. On my computer, the threshold is at 131459071-131459072 for 4-byte integers. Performance abruptly degrades at the threshold. It also has the unfortunate bug-hiding effect that programs can work properly with the small algorithm and fail when inputs get large enough. Finally, at large inputs, the C++ STL implementation becomes comparable. Here are some counts to the number of calls to the comparison function for an array initialized by a[0]=1 a[n+1]= a[n]*1664525+1013904223

qsort
 131459070 easy  0        hard 3333417997
 131459071 easy  0        hard 3333417454
 131459072 easy  50294519 hard 4063553331
 268435456 easy 102684870 hard 8680917338

C++ STL sort()
 131459070 easy 15139169 hard 4345836000
 131459071 easy 15141479 hard 4316599909
 131459072 easy 15139606 hard 4470743742
 268435456 easy 30917419 hard 9444799480

The columns give the number of "easy" comparisons (pa==pb for qsort; a==b for sort) and "hard". The PRNG has period 2^32 so every number is unique.