We should clarify that we restrict it to sorted input right here.
Based on the description it sounds like the encoding would be valid even on unsorted input (the overhead wouldn't even be that significant as the 0 prefix length would be RLE'd) and could save space if there's some prefix similarity in the data. (Just a thought)