Incorrect sorted flag after concat

[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

import polars as pl

df = pl.DataFrame({"x": [0, 1, 1], "y": ["B", "B", "A"]}).with_columns(
    pl.col("y").cast(pl.Categorical(ordering="lexical"))
)
df2 = pl.concat(part.sort("y") for part in df.partition_by("x"))

assert df2["y"].is_sorted()  # This is incorrect!
print(df2)

Output:

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

Issue description

Similar bug to #15072.

Possibly related to #15708, which I do not consider a low-priority bug.

• Categorical dtypes are a much more mainstream feature than e.g. nested dtypes.
• Lexical ordering is probably what most users want, so I don't consider it niche.

Expected behavior

Correctly detect that B, A, B is not sorted.

Installed versions

--------Version info---------
Polars:               0.20.21
Index type:           UInt32 
Platform:             Windows-10-10.0.19045-SP0
Python:               3.11.4 | packaged by conda-forge | (main, Jun 10 2023, 17:59:51) [MSC v.1935 64 bit (AMD64)]

----Optional dependencies----
adbc_driver_manager:  0.5.1
cloudpickle:          <not installed>
connectorx:           <not installed>
deltalake:            <not installed>
fastexcel:            0.9.1
fsspec:               2023.4.0
gevent:               <not installed>
hvplot:               <not installed>
matplotlib:           3.8.2
nest_asyncio:         1.5.6
numpy:                1.26.4
openpyxl:             3.1.2
pandas:               2.2.2
pyarrow:              15.0.2
pydantic:             2.6.4
pyiceberg:            <not installed>
pyxlsb:               <not installed>
sqlalchemy:           2.0.29
xlsx2csv:             0.8.1
xlsxwriter:           3.1.2

[swapdewalkar]

@stinodego Can I take this up?

[c-peters]

@swapdewalkar ,Yes go for it!

[MarcoGorelli]

thanks for the report - bumping this up to high after discussion today, as incorrect sorted flags can potentially lead to incorrect results