table.sortRange(table, startIndex, endIndex, comparator)

Feature Requests Engine Features
#1

One very useful thing Lua’s table library is missing that many other languages have is a sort function that acts only on a specified range. One alternative is to create a sub-table and then load in all the values within range from the original table to the sub-table and then call table.sort on the sub-table. This can be pretty expensive for large ranges. The other alternative is to write a sorting function from scratch, which is guaranteed to be much slower than the C version and could require lots of code.

2 Likes
#2

Any sorting function is guaranteed to be O(nlogn) at best. The method of creating a subarray and then re-inputting that subarray is roughly theta(n).

So in order for this idea of creating a subarray and then reinputting to be so slow it isn’t worth doing in Lua, your n (or size of subarray) must be at least half the size of (xlogx - nlogn) where x is the size of the total array.

I would say that such an optimization is mostly insignificant, and it’s actually not a half bad idea to go through with this subarray plan.

4 Likes
#3

I’m not so sure about that, as with using table.sort, you’re crossing that weird C-boundary for invoking .sort and for invoking the comparator x times.

1 Like
#4

I’m skeptical. What is it that you’re trying to do that is so unacceptably slow?

1 Like