Sorted Collection

Introduction

A Sorted Collection is a data structure that maintains its elements in a specific sorted order, based on either their natural comparison (e.g., numeric or lexicographic) or a custom-defined key. Unlike typical unordered collections such as sets or hash maps, sorted collections provide deterministic ordering, which makes them invaluable in applications requiring:

Fast access to minimum/maximum elements
Range queries
Binary searches
Efficient priority-based operations

Sorted collections are fundamental in algorithms and systems that demand predictable ordering and efficient querying.

What Is a Sorted Collection?

A sorted collection is any collection (like a list, set, map, etc.) where the elements are automatically ordered based on a comparison function. This ordering is maintained during insertion, deletion, and iteration.

Example:

If you insert elements into a sorted collection in any order:

collection.add(5)
collection.add(2)
collection.add(8)

The internal structure will maintain them as:

[2, 5, 8]

Common Types of Sorted Collections

Type	Key Property	Example Implementation
Sorted List	Allows duplicates, ordered	Python `SortedList`
Sorted Set	Unique elements, ordered	Java `TreeSet`, Python `SortedSet`
Sorted Map	Key-value pairs in key order	Java `TreeMap`, C++ `map`
Priority Queue	Partially sorted (by priority)	Heap, `PriorityQueue`

Benefits of Sorted Collections

Ordered iteration: Guarantees sorted traversal.
Efficient range lookups: Binary search or logarithmic access.
Minimum/maximum access: Often in constant or log time.
Insertion with order: Maintains sorting without full re-sorting.

Underlying Data Structures

Sorted collections are typically backed by self-balancing binary search trees, heaps, or skip lists.

1. Balanced Binary Search Trees

Examples: Red-Black Tree, AVL Tree
Maintains O(log n) insertions, deletions, and lookups.
Used in Java’s TreeSet, TreeMap, and C++’s std::map.

2. Skip Lists

Probabilistic alternative to trees
Used in some Redis and concurrent implementations

3. Binary Heaps (Min/Max Heap)

Maintains partial ordering: parent ≤ children (min heap)
Ideal for priority queues, not full sorted iteration

4. Arrays with Binary Search (`insort`)

Used when data is mostly read and only occasionally updated
Python’s bisect module and SortedList use this approach

Sorted Collection in Python

Using `bisect` for manual sorted insertion

import bisect

lst = []
bisect.insort(lst, 5)
bisect.insort(lst, 2)
bisect.insort(lst, 8)
print(lst)  # [2, 5, 8]

Using `sortedcontainers` library

from sortedcontainers import SortedList

sl = SortedList()
sl.add(3)
sl.add(1)
sl.add(2)
print(sl)  # SortedList([1, 2, 3])

SortedList: list with fast binary-search-based insertions
SortedSet: unique elements
SortedDict: key-value store with sorted keys

Sorted Collection in Java

TreeSet

import java.util.TreeSet;

TreeSet ts = new TreeSet<>();
ts.add(5);
ts.add(1);
ts.add(3);
System.out.println(ts);  // [1, 3, 5]

TreeMap

import java.util.TreeMap;

TreeMap map = new TreeMap<>();
map.put("b", 2);
map.put("a", 1);
System.out.println(map);  // {a=1, b=2}

Sorted Collection in C++

Using `std::set` (sorted, unique)

#include 
std::set s = {4, 1, 3};
for (int x : s) {
    std::cout << x << " ";
}
// Output: 1 3 4

Using `std::map`

#include 
std::map m;
m["zebra"] = 3;
m["apple"] = 1;
// Output: apple 1, zebra 3

Use Cases for Sorted Collections

Domain	Use Case
Search engines	Sorted indexes for keyword ranking
Finance	Ordered transaction books
Databases	Range queries and ordered scans
Algorithms	Sliding window min/max, LIS, sweep line
Real-time systems	Priority queues and scheduling
Caches	Expiry-based eviction policies

Sorted Collection vs Unsorted Collection

Feature	Sorted Collection	Unsorted Collection
Iteration Order	Deterministic (sorted)	Arbitrary
Search Performance	Binary Search (O(log n))	Hashing (O(1) avg)
Range Queries	Efficient	Not supported
Insertion Speed	Slower (O(log n))	Faster (O(1) in lists/sets)
Duplicates	Depends on implementation	Usually allowed

When to Use Sorted Collections

✅ Choose sorted collections when:

You need ordered access
You’re performing binary searches or range-based operations
You want predictable iteration
You’re optimizing for read-heavy workflows

❌ Avoid sorted collections when:

Performance for frequent insertions is critical
Sorting is irrelevant
Uniqueness or hashing is more important (e.g., dictionaries)

Performance Comparison

Operation	`SortedList`	`SortedSet`	`Heap`	`Unsorted List`
Insertion	O(log n)	O(log n)	O(log n)	O(1)
Lookup	O(log n)	O(log n)	O(n)	O(n)
Iteration	O(n) (sorted)	O(n)	Unordered	Unordered
Delete	O(log n)	O(log n)	O(log n)	O(n)
Min/Max Access	O(1)	O(1)	O(1)	O(n)

Limitations of Sorted Collections

Insertions and deletions are slower than unsorted collections
Additional memory overhead for tree balancing or skip-list layers
Cannot always support constant-time updates
Custom comparators may lead to unexpected ordering if not well-defined

Custom Sorting with Keys

Many sorted collection libraries support custom key functions.

Python example:

from sortedcontainers import SortedList

sl = SortedList(key=lambda x: x[1])  # sort by second item in tuple
sl.add(('A', 3))
sl.add(('B', 1))
sl.add(('C', 2))
print(list(sl))  # [('B', 1), ('C', 2), ('A', 3)]

This is powerful for ordered processing based on priorities, timestamps, or weights.

Summary

A Sorted Collection is a versatile data structure that provides automatically ordered elements and supports efficient binary search, iteration, and range operations. They are implemented using trees, heaps, or bisect-based arrays and come in several forms: lists, sets, and dictionaries.

Whether you’re building an algorithm, a database engine, or a financial app, sorted collections are essential for structure, performance, and correctness in ordered data processing.