On-chain sorting optimization

Question

I have array of structures on-chain and need to sort it. I used one of that quicksort algorithms that easily can be found and adopted it to use structures instead of plain uints. But I dislike it because it requires "swap" operation - change places of 2 items is the array. With structures it is possible only by creating memory instance like MyStruct memory temp and copy one of swappables there, then replace it and put memory-stored one into copied place. It is expensive.

I though that I could use mapping like mapping (uint16 => MyStruct) list and then just "swap keys". But it seems that with mapping I have to to the same - copy values because I cannot change key values.

Am I missed something or mapping cannot helps me here?

Answer 1

You cannot swap keys in your example, that would result in creating new mapping entries, with high cost as you already said. But you could use the mapping mapping (uint16 => MyStuct) list to store the data, while you put your keys (the uint16 values) in an array. You can sort the keys in the array then, the swap operation there will be cheaper. The data itself will be read from the mapping.