A collection of items that can be accessed in an ordered fashion. Allows items to be inserted or removed by position. This is unlike an associative collection, such as a Map, or a Set that does not allow clients to positionally insert elements. Only an ordered collection can be sorted. If you have an un-ordered bag of elements, sorting them has no effect since its elements cannot be positionally accessed -- i.e. One cannot ask ''is first element greater than second element?''.


''You're confusing ordering with sequence, I think.  Among the various types of sorted collections you can have are:''

	* ''Ordered set/bag.  Ordering does make sense here--as iteration through the collection can be made to proceed in an ordered fashion.  (Compare with a hashtable, for which such a traversal will provide the elements in an arbitrary, though deterministic, order).''

	* ''Ordered map/dict/multiset.  Similar to set/bag.  You can retrieve elements by key, obviously; but an iteration will proceed through the collection in a defined order''

	* ''Ordered array.  Elements are accessed (usually) by integers in range [0 .. size-1] or [1 .. size]; invariant that a(x) <= a(y) for all x<y is maintained.  Compare with an ordinary array; where the order of elements is the order of insertion (or changes only according to explicit order-changing operations by the program).''