Performance Regression in Sorting between 1.9.0 and 1.12.0

[J-Meyers]

Checks

• I have checked that this issue has not already been reported.
• I have confirmed this bug exists on the latest version of Polars.

Reproducible example

import polars as pl
df = pl.scan_parquet("output2.parquet").select("col_A", "col_B", "col_G").collect()
df = df.sort("col_G")
df = df.select("col_A", "col_B")
df = df.explode(pl.all())
df = df.slice(0, 100_000) # this isn't needed to reproduce, but makes the timing much shorter so is nice
# This is the relevant part timing wise
df.sort("col_A")

Uploaded as a .txt file, but its really a .parquet just rename it

output2.txt

Log output

No response

Issue description

In version in 1.9.0 this takes very little time 27ms for the sort, but in version 1.12 it takes > 2 seconds on my laptop, the initial sort is needed for the bug to show up - I am currently using u64-idx, but I doubt it makes a difference

If instead of selecting an array of list column at the beginning I instead selected a array of int column the sorting speed difference disappears

Expected behavior

The timing should still be really fast in the ms range not in seconds

Installed versions

--------Version info---------
Polars:              1.12.0
Index type:          UInt64
Platform:            Linux-5.15.0-124-generic-x86_64-with-glibc2.31
Python:              3.11.9 (main, Oct  8 2024, 17:30:19) [GCC 13.1.0]
LTS CPU:             False

----Optional dependencies----
adbc_driver_manager  <not installed>
altair               <not installed>
cloudpickle          3.0.0
connectorx           <not installed>
deltalake            <not installed>
fastexcel            <not installed>
fsspec               2023.9.2
gevent               <not installed>
great_tables         <not installed>
matplotlib           3.9.2
nest_asyncio         1.6.0
numpy                1.26.4
openpyxl             <not installed>
pandas               2.2.3
pyarrow              17.0.0
pydantic             2.9.2
pyiceberg            <not installed>
sqlalchemy           <not installed>
torch                2.4.1+cu124
xlsx2csv             <not installed>
xlsxwriter           <not installed>

[cmdlineluser]

It seems it got slow after #19327

[ritchie46]

@coastalwhite I shall take a look tomorrow first. If it is that gather, it's my bad.

[coastalwhite]

Yeah that PR is definitely the problem. There seems to be some exponential behavior introduced by take_unchecked. Here is a profile on a debug and release.

[nameexhaustion]

Uploaded as a .txt file, but its really a .parquet just rename it

Security at its finest 🫠