Better Documentation to Describe Storage Map Sorting

[humanalgorithm]

Per CosmWasm Discord, question and answer between me and @ethanfrey

Question:

Hello devs
I am working in the storage-plus repo and I found what I believe is a weird bug with IndexedMap/storage

If I put the following pk key data into an IndexedMap:

        let pk1 = ("grow1", "5627");
        let pk2 = ("grow2", "5628");
        let pk3 = ("sing1", "5629");
        let pk4 = ("zing", "5630")

then do a simple range order Ascending with no prefix I get

[("zing", "5630"), ("grow1", "5627"), ("grow2", "5628"), ("sing1", "5629")]

now if I change "zing" to "zing1" then do a range I get

[("grow1", "5627"), ("grow2", "5628"), ("sing1", "5629"), ("zing1", "5630")]

Unless I'm missing something pretty sure this is a low level bug in the sorting order. Note that this only happens when numbers and letters are mixed in the key, if its all numbers or all letters then it prints it out alphabetically.

What I'm doing here is a modified version of the test here:
https://github.com/CosmWasm/cw-plus/blob/main/packages/storage-plus/src/indexed_map.rs#L1069

Answer:

Ethan Frey: this is odd but expected behavior.
if the items are all the same length (like Addr) or binary encoded (like u64), then they will be sorted properly.

However, stings and byte slices are all length prefix encoded, so shortest goes first... but only in prefixes.

this was needed to properly separate prefixes from suffixes, but you hit a case where it doesn't work as the user would assume and should be documented