Or do i call Sort on Vector<> / Array<> before i need it sorted or use the GetSortOrder() call?
In most cases, GetSortOrder for Index / ArrayMap / VectorMap is the best aproach (also generally faster than the cost of maintaining nodebased tree structure like std::map).