lexsort_to_indices may output larger size than input

[jychen7]

Describe the bug
Not sure if it is arrow-rs bug. This issue is created to track
We find a problem in apache/datafusion#3747 (comment)

To Reproduce
TBD

Expected behavior
sort output size should be <= input size (smaller is expected when it is partial sort, i.e. top K)

Additional context

[tustvold]

I don't think the size of the underlying buffers is something we guarantee, whilst one could argue that we should correctly estimate the output buffers to not be larger than the inputs, this is not guaranteed.

Perhaps you might explain why this is a problem?

Edit: I'm also a little confused as the DataFusion issue does not appear to relate to lexsort_to_indices but seems to be about MutableArrayData?

[tustvold]

Closing this as I've not heard back, feel free to reopen if still an issue

[jychen7]

one could argue that we should correctly estimate the output buffers to not be larger than the inputs, this is not guaranteed.

Thanks, that makes sense