Describe the bug
The standard requires nth_element (both std and std::ranges overloads) to perform only O(n lg n) swaps. However, we currently implement only quickselect:

This has worst case running time O(n^2) if we always choose bad pivots, just like quicksort. We need some form of 'ideal' checking similar to how std::sort works, and fall back to a median-of-medians or similar implementation.

Additional context

This was previously recorded in a Microsoft-internal bug database but I closed the issue there as I had filed it against myself.