`Array.qsort` has quadratic runtime on constant arrays

Prerequisites

Please put an X between the brackets as you perform the following steps:

• Check that your issue is not already filed:
  https://github.com/leanprover/lean4/issues
• Reduce the issue to a minimal, self-contained, reproducible test case.
  Avoid dependencies to Mathlib or Batteries.
• Test your test case against the latest nightly release, for example on
  https://live.lean-lang.org/#project=lean-nightly
  (You can also use the settings there to switch to “Lean nightly”)

Description

def m (n : Nat) := Array.range n
def l (n : Nat) := Array.replicate n 0

#eval ((m 100000).qsort).size -- this is fast
#eval ((l 100000).qsort).size -- this is slow

The problem is that we split the list into "less than pivot" and "greater than or equal to pivot" in a naive way, leading to partition calls of size n, n - 1, n - 2 and so on. Solutions are discussed on Wikipedia; options include using a pivoting procedure like the Hoare rule where an all-equal array returns the center index as the pivoting index, or partitioning the array into three parts: less than pivot, equal to pivot or greater than pivot.

Expected behavior: Quicksort does not take quadratic time for reasonable inputs

Actual behavior: Quicksort takes quadratic time if all inputs are equal

Additional Information

This is apparently the bottleneck in the workspace symbol search LSP request!

Versions

nightly-2025-04-24

Impact

Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.

Reproduce the issue with the Array.qsort examples using Array.range and Array.replicate, then inspect the Array.qsort entry point and its partitioning behavior. Compare the repeated-elements options described in the issue. Done means constant arrays no longer exhibit quadratic runtime while the reported qsort behavior remains correct.