Как создать отсортированную карту в Scala (изменяемой / неизменяемой)?
Используйте TreeMap.
TreeMap
Всегда есть java.util.TreeMap, который, хотя и не так хорош, как карты Scala, вероятно, именно то поведение, которое вы ищете.