Regression: Incorrect categorical encoding after sort

[s-banach]

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

The following code gives correct output in 1.12 but incorrect in 1.13.

import polars as pl

df = (
    pl.DataFrame({"x": pl.Series("x", ["a", "b"], dtype=pl.Categorical), "y": [1, 1]})
    .slice(1)
    .sort("x")
    .with_columns(pl.col("x").to_physical().name.suffix("_physical"))
)
print(df)

Log output

No response

Issue description

Incorrect output:

shape: (1, 3)
┌─────┬─────┬────────────┐
│ x   ┆ y   ┆ x_physical │
│ --- ┆ --- ┆ ---        │
│ cat ┆ i64 ┆ u32        │
╞═════╪═════╪════════════╡
│ b   ┆ 1   ┆ 0          │
└─────┴─────┴────────────┘

In other words, the categorical encoding has changed.
Now if I try to join this dataframe back to the original data, I will get performance warnings that the encodings don't match, and they will have to be re-encoded before they can be joined together.
Users of my code will think I'm incompetent, because they're getting all these warnings.

Expected behavior

Correct output:

shape: (1, 3)
┌─────┬─────┬────────────┐
│ x   ┆ y   ┆ x_physical │
│ --- ┆ --- ┆ ---        │
│ cat ┆ i64 ┆ u32        │
╞═════╪═════╪════════════╡
│ b   ┆ 1   ┆ 1          │
└─────┴─────┴────────────┘

Installed versions

--------Version info---------
Polars:              1.14.0
Index type:          UInt32
Platform:            Windows-11-10.0.22631-SP0
Python:              3.12.7 (main, Oct 16 2024, 00:21:24) [MSC v.1929 64 bit (AMD64)]
LTS CPU:             False

----Optional dependencies----
adbc_driver_manager  <not installed>
altair               <not installed>
boto3                1.35.47
cloudpickle          <not installed>
connectorx           <not installed>
deltalake            <not installed>
fastexcel            0.12.0
fsspec               <not installed>
gevent               <not installed>
google.auth          <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           2.0.36
torch                <not installed>
xlsx2csv             <not installed>
xlsxwriter           <not installed>

[coastalwhite]

I don't think we give any guarantees about this. If you want your encoding to stay consistent, I think you should use a string_cache.

[s-banach]

I hope polars can offer an ergonomic way to cast all categorical columns to Enum to guarantee the encodings don’t change.