Every item contains a key from a linearly ordered data type K , called the key type of S , and an information from a data type I , called the information type of S . The number of items in S is called the size of S . A sorted sequence of size zero is called empty.
Sorted sequences are a very powerful data type.
They can do everything that dictionaries and priority queues can do. The key type K must be linearly ordered. The linear order on K may change over time subject to the condition that the order of the elements that are currently in the sorted sequence remains stable. An application of sorted sequences where the linear order on the keys evolves over time is the plane sweep algorithm for line segment intersection. This algorithm sweeps an arrangement of segments by a vertical sweep line and keeps the intersected segments in a sorted sequence sorted according to the y-coordinates of their intersections with the sweep line.