Explain the significance of the Sorted interface in the context of SortedMap.

The Sorted interface in the context of SortedMap indicates that the map stores its elements in a sorted order by keys. This means:

• Keys are ordered according to their natural ordering (if they implement Comparable) or with the help of a provided comparator.
• Methods that return a set of keys or a subset (such as subMap, headMap, tailMap) return elements in sorted order.

Thus, SortedMap guarantees that during iteration, elements will be in a specific order, which is convenient for range queries and ordered output.

Example of using TreeMap (implementation of SortedMap):

SortedMap<Integer, String> map = new TreeMap<>();
map.put(3, "Three");
map.put(1, "One");
map.put(2, "Two");

for (Integer key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}
// Output will be in key order: 1, 2, 3