Sorting, Searching, & Selection

So far this chapter has dealt primarily with structural ordering; that is, the fundamental concepts around memory layouts and access mechanisms used to store and organize data. The material has not yet addressed any meaningful ways to arrange elements by their realtive values. This page introduces the concept of comparative ordering which defines how elements can be meaningfully compared and used to produce sorted arrangements.

By establishing a comparison relation on the collection’s elements it is possible to start reasoning about sorting algorithithms and other order-dependent operations, including solutions to tasks such as searching and selection. Searching here means matching an element by value or predicate within a collection, and selection provides a way to find elements via rank-based comparisons, such as the kth-smallest (or largest) element in a collection. Both searching and selection support queries over single elements or ranges within the underlying collection; searching operates over values (including value ranges), while selection operates over ranks (including ranges of ranks).

Both searching and selection are represented here as fundamental operations in data structures and differ significantly from what is commonly referred to as “search” in real-world systems such as web search engines like Google or DuckDuckGo. Large-scale web search systems operate in a different problem domain known as information retrieval. They do not scan collections directly; instead, they rely on large-scale indexing structures (such as inverted indexes), distributed storage, and ranking algorithms to efficiently retrieve and order relevant documents. While these systems make use of fundamental data structures and search primitives, the overall problem is substantially more complex and extends beyond the scope of basic searching and selection.

Comparative Ordering

Structural ordering defines the mechanics of data structures and algorithms, it dictates how data is physically laid out and traversed. By contrast, comparative ordering governs value-based ordering semantics and the correctness of order-dependent operations. Examples of order-dependent operations include sort operations on lists, insert and remove operations on structures that maintain sorted invariants, and query operations such as find (search), and find_kth ranked elements (selection) within a collection.

Most DSA texts state that sorting a collection typically assumes a total order on the values to be sorted, or more generally, a consistent comparison relation on those values. The text might even further define a total order as a partially ordered set where every pair of values is directly comparable, but not much more is typically provided. Programming languages handle this idea different. Some language philosophies abstract this away almost entirely, but it is still important to understand what these terms mean, specifically for Rust, in order to implement sorted arrangements on custom types. This section provides a brief overview of some discrete mathematics concepts that are used to define comparative ordering and how to guarantee it.

The idea of comparative ordering as defined in this module is based loosely on elementary order theory, which itself is formulated in terms of binary relations to establish a comparative ordering of values. One of the most familiar examples of order theory, and math in general, is numerical ordering via magnitude. This is often introduced early on through story problems concerning two or more parties who possess and/or exchange multiples of the same object. For example, “If Peter had 3 drinks and Jeanine had 2 drinks, who had more drinks?” In this way, it is possible to establish the concept of numerical ordering through a binary relation.

Mathematically, a binary relation R is a subset of the Cartesian product of two sets A and B, which can be written as R ⊆ A × B. This relation defines the collection of all ordered pairs for which the relation holds true. In ordering and comparison contexts, it is most common to work with relations over a single set, so that R ⊆ A × A. In this setting, a comparison between two elements x and y can be expressed as (x, y) ∈ R, meaning that the ordered pair (x, y) belongs to the relation. This can also be written equivalently using infix notation as xRy.

A binary relation can be described in two equivalent ways; extensionally, as a set of ordered pairs, or intensionally, as a predicate (or comparative function in computer science) P(x, y) that determines whether a given pair belongs to that set. In practice, algorithms evaluate the predicate for individual pairs, but the underlying relation is defined mathematically as the set of all pairs for which the predicate evaluates to true. This can be re-stated by saying that the predicate P(x, y) evaluates to true if and only if (x, y) ∈ R, that is, if and only if the ordered pair (x, y) belongs to the relation. These two perspectives are equivalent; the predicate characterizes the relation, while the relation is the set of all pairs for which the predicate evaluates to true.

As an analogy, consider a coordinate plane (2d graph) representing a relation defined by the predicate “less than”, written as P(x, y) = (x < y). The graph illustrates the relation as region encompassing a set of all points (x, y) such that x < y. The position of elements in an ordered pair matters. For example, the relation R = “less than” on the set A = { 1, 2, 3 } can be written as R = { (1,2), (1,3), (2,3) } ⊆ A × A, and does not include reversed pairs such as (2,1) or (3, 1). For the relation “less than”, if (x,y) ∈ R, then (y,x) ∉ R, illustrating its asymmetry. Stated slightly differently, evaluating an expression in code like 2 < 3 corresponds mathematically to checking whether the pair (2, 3) belongs to this relation.

As illustrated, the “less than” relation is asymmetric. Asymmetry is only one of many possible properties that a relation may satisfy. While not exhaustive, the following properties are useful for classifying relations relevant to comparative ordering:

Transitivity

If k1 <= k2 and k2 <= k3, then k1 <= k3. For strict relations, this applies to the _< _ operator such that if k1 < k2 and k2 < k3, then k1 < k3.

Reflexivity & Irreflexivity

Reflexivity holds when k <= k. In contrast, irreflexivity holds when k !< k, and is a defining property of strict relations. This can be expressed in mathematical notation as ¬(k < k).

Antisymmetry

Antisymmetry occurs when k1 <= k2 and k2 <= k1 imply k1 == k2. This ensures that no two distinct elements relate in both directions unless they are the same.

Asymmetry

Asymmetry holds when k1 < k2 implies k2 !< k1. This enforces a one-way relationship and implies irreflexivity.

Comparability

Every pair of elements must be comparable, which distinguishes total ordering from partial ordering: k1 <= k2 || k2 <= k1. That is, for all elements x and y, either x <= y or y <= x.

An ordering scheme, such as a partial order or total order, is a classification of relations based on the mathematical properties they satisfy. There are many relations and ordering schemes in mathematics, but for comparative ordering in computer science, the most important ordering schemes are categorized in the following table.

Ordering Scheme	Transitive	Reflexive	Symmetry	Comparability
Total Order	X	X	Antisymmetric	X
Strict Total Order	X	(Irreflexive)		X
Total Preorder	X	X		X
Partial Order	X	X	Antisymmetric
Strict Partial Order	X	(Irreflexive)	Asymmetric

It is important to note that a single ordering scheme may be characterized by multiple equivalent predicates, which define the same underlying relation in different ways. For example, a non-strict total order can be defined directly using the predicate P(x,y) = (x <= y), or equivalently in terms of a strict order using x !< y (i.e., it is not the case that y < x). These formulations describe the same ordering structure, but differ in how the relation is expressed.

Different ordering schemes arise when the underlying relational properties change. A strict partial order is irreflexive and transitive but does not require comparability between all elements. In contrast, a total preorder is reflexive and transitive, but does not require antisymmetry, allowing distinct elements to be equivalent under the relation (i.e., “ties”), even when they are not equal.

Compositional Ordering Constructions

Compositional ordering constructions are not a formally categorized type of ordering, but for the purposes of this module describe how comparison relations are defined over structured values. These constructions determine whether values are compared as indivisible units or as structured collections of components. This section discusses two common comparison constructions.

• Atomic ordering represents the simplest kind of logical ordering, and refers to comparisons performed on values treated as indivisible units using a defined comparison relation. Numerical ordering, one of the most common instances of atomic ordering, is where values are compared according to their numeric magnitude. A simple example of numerical ordering is the inequality 2 < 3. For example, the following array of integers is sorted under numerical (and thus atomic) ordering: [1, 2, 5, 10, 11, 23]

• Lexicographical ordering, sometimes called dictionary ordering, represents another common logical ordering scheme which generalizes alphabetical ordering to sequences over a totally ordered set. Lexicographical ordering is used to compare composite objects of elements. This is generally done in sequential order, one at a time. In Rust, the String type represents a contiguous UTF-8 encoded sequence of bytes, so comparisons between strings are performed lexicographically over UTF-8 bytes in sequence. For example, imagine two files named file_6 and file_10. It might be natural for a human to assume that file #6 comes before file #10, but that is not necessarily how a computer compares the values. When computing a lexicographical ordering, the first five UTF-8 bytes of each file name are equal and therefore do not affect the comparison. However, the sixth byte differs, and since “1” < “6” in ASCII, file_10 comes before file_6.

      "10" < "6" // lexicographically true
      10 > 6     // numerically true

Comparative Ordering In Practice

The next logical question is, how is it possible to achieve a partial order, total preorder, and total order in programming? This is a question that varies across languages due to design philosophy differences.

The next chapter talks about keying schemes in greater detail. For now, just know that Rust provides the Ord and PartialOrd traits to define ordering bounds on custom types. When implementing types that require Ord, such as within structures that maintain a sorted invariant, you must also implement Eq, PartialEq, and PartialOrd. Together, these traits define the comparison rules needed to establish a total order. The Ord trait defines a total order relation by way of a concrete cmp (“comparison”) method. To allow for ties, such as in a total preorder, you define a comparison predicate (key function or comparator) within the sorting operation, rather than in the trait implementation itself.

The following code example illustrates how Rust’s PartialOrd and Ord traits relate to mathematical ordering concepts. The PartialOrd implementation defines a total preorder: a reflexive, transitive relation where all pairs of elements are comparable, but ties are allowed, such as when two students receive the same grade. The Ord implementation refines this into a total order by breaking ties deterministically using lexicographical ordering within the student’s name field as the tie breaker.

In other words, PartialOrd specifies the predicate that determines whether one element should be considered less than, equal to, or greater than another (allowing equivalence), while Ord guarantees a fully deterministic ordering of all elements by resolving any ties. Rust’s trait names can be misleading; PartialOrd does not strictly enforce a partial order in the mathematical sense (which is irreflexive and asymmetric), but instead allows for any pairwise-comparable relation, including total preorders.

#[derive(Debug, Eq, PartialEq)]
struct Student {
    name: &'static str,
    grade: u8,
}

// Implements PartialOrd for a total preorder
impl PartialOrd for Student {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        // Compare by grade
        Some(self.grade.cmp(&other.grade))
    }
}

// Implements Ord for a deterministic total order
impl Ord for Student {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // First compare by grade
        let grade_order = self.grade.cmp(&other.grade);
        if grade_order == std::cmp::Ordering::Equal {
            // Break ties by name to get a total order
            self.name.cmp(other.name)
        } else {
            grade_order
        }
    }
}

Sorting

This section only briefly covers some of the common (elementary) sorting algorithms for list structures. The chapter on hierarchies covers some of the most common sorted structures in more depth with self-balancing search trees, and this page introduces the module’s first sorted structre; the skip list. In both cases, sorted arrangements are useful for performing efficient lookups within a collection. Lookups, including identifying elements in the collection, identifying kth largest/smallest elements, and retrieving ranges of values in a collection are covered in subsequent sections on searching and selection.

Sorting can be defined as the logical arrangement of elements in a collection into a sequence that adheres to a given comparison relation. A sorted arrangement of elements is determined by the comparison relation and exists independently of the collection’s physical layout (structural ordering). In some cases, sorting algorithms achieve this by rearranging elements in memory. This is true for most sort operations on list structures. In other cases, data structures maintain a sorted traversal order by storing links to elements as pointers or indices without physically reordering the underlying storage. In both cases, the collection is considered sorted if the sequence produced by iteration satisfies the comparison relation.

Naturally, comparison-based sorting requires that the comparison relation define either a total preorder (<=p) or a total order (<=), such that every pair of elements is comparable. In this way, the ordering is a property of a relation defined on a set of elements, whereas sorting is the process of arranging elements according to that relation.

In the comparison-based model, it can be shown that any sorting algorithm requires Ω(n * log(n)) comparisons in the worst case. This holds true for both sorting a list or maintaining a sorted structure. For example, inserting a comparable element into a self-balancing search tree requires O(log(n)) time, so constructing such a tree from n elements yields a de-facto O(n * log(n)) sorting method. Later pages in this module cover more advanced algorithmic material including non-comparison-based sorting such as radix sort which runs in roughly linear time (O(d * n)) where d is the number of digits in each element.

In practice, the differences between choosing a sorting algorithm vs a sorted data structure primarily depend on factors such as input size, the degree to which inputs are already sorted, and memory usage. The reason to choose a sorted structure over performing periodic sort operations on a list comes down to whether a sorted invariant is essential to the design requirements of the program.

Definition

A sorting algorithm is said to occur “in-place” if its auxiliary memory complexity (the space used for things other than the input itself) is O(1). This condition is sometimes extended to O(log(n)) to account for the call stack. If a secondary structure is used that is O(n) in size, it is no longer considered “in-place”. In-place algorithms must manipulate the data within the original memory block, using only a tiny, constant amount of “scratchpad” space (like a single temp variable for swaps). This means that in-place sorting algorithms can only take mutable objects.

Insertion & Selection Sort

The two algorithms listed here are similar enough to lump together. Both sorting algorithms separate an unsorted base collection into sorted and unsorted logical segments during operation. With each pass, the sorted segment increases by one, and the unsorted segment decreases by one. For the first pass, the 0th element can be considered trivially sorted. Both algorithms can be implemented in place, or with a secondary structure of n elements.

As a potentially reductive generalization, think of insertion sort as finding the right spot for the next element, and selection sort as finding the right element for the next spot.

Insertion Sort

The insertion sort algorithm proceeds linearly through the unsorted collection, figuring out where in the sorted segment to insert the unsorted element. The insertion then results in O(n) shifts to the right. This requires n number of O(n) scans of the sorted segment, and n number of O(n) shift operations, resulting in a total O(n^2) running time and O(n^2) number of writes. The name comes from the way the algorithm inserts elements into a sorted segment.

Selection Sort

Selection sort proceeds linearly through the base collection, figuring out the next non-increasing/decreasing element within the unsorted section to append to the sorted segment. This requires n number of O(n) scans of the unsorted segment, and n number of O(1) swap operations resulting in O(n^2) running time and O(n) number of writes (swaps).

Selection sort represents a simple and effective sorting algorithm, but only for small sets because of its quadratic temporal tendancy.

Merge Sort

Quick Sort

Sorting Analysis

It should be noted that the underlying data structure can alter the operational profile of these algorithms. For example, implementing insertion sort on a linked list rather than an array changes the insertion cost from shifting elements (O(n) writes) to pointer updates (O(1) writes), though the search cost remains the same.

By their descriptions, selection sort may appear more efficient as it performs significantly fewer writes (O(n) vs O(n^2)). This is true and makes it useful when writing to memory is expensive. However, selection sort is generally unstable, meaning that it may reorder unique elements of equal value within the base collection, whereas insertion sort is generally stable. Furthermore, insertion sort is adaptive; it becomes significantly faster (O(n)) on nearly-sorted data, whereas selection sort is always (O(n^2)).

Searching

The concept of searching can be defined here as determining whether a given element or key exists in a collection. The next chapter on associative structures goes into more detail about key-value pairs and provides a way to achieve O(1) searches, but this requires specialized structures known as maps. Searches in unsorted sequences necessarily require O(n) time, and can be improved to O(log(n)) time for sorted sequences.

Binary Search

The most popular and practical search algorithm is called binary search. The idea of binary search within a sequence structure is simple, but requires that the sequence optimally provide random access such as array indexing, and also requires that the sequence be sorted. Within a sorted list, you start at the half-way point and compare the value against the search key. If the value is the same, you end the algorithm. If the value is smaller or larger than the value half-way through the sequence, you’ve already eliminated roughly half of all necessary comparisons. The search algorithm continues halving the remaining candidate values until it either finds the key or determins that the key is not in the sequence.

Selection

Selection, often referred to as order statistics, concerns rank-based queries over a collection. These ranks are typically expressed as the kth element, such as the kth smallest or largest value in the collection. Selection can be performed on both unsorted and sorted collections, but have different complexity characteristics. In unsorted collections, comparison-based algorithms such as randomized quickselect can identify the kth element in expected O(n) time where n is the number of elements in the collection. In contrast, sorted collections can support more efficient order statistic queries. If the underlying structure provides O(1) random access, such as with an indexed array, the kth element can be retrieved in O(1) time because the index value encodes the element’s rank out of the box. Sorted structures also make range queries more efficient and direct. For example, retrieving the elements ranked 3rd through 6th can be done by simple index-based access in a sorted list, or by sequential traversal in structures that maintain a sorted invariant. Because sorted arrangements provide such a large advantage to selection, it is common to use sorted structures where frequent selection is required. The next section introduces this module’s first sorted structure, the skip list, which is a probabilistic data structure that maintains sorted order and supports efficient search queries in O(log(n)) time and range queries in O(log(n) + k) time where k is the size of the range.

Quickselect

• Used to find the kth smallest/largest element in an unsorted array in O(n) time
• Used for efficient partial order statistics
• By comparison, kth values in sorted sets are O(1)

The Skip List ADT

• Introduction to the first sorted structure of the module
• Probabalistic vs deterministic sorted structures
• Design patterns??? (towers, layers, etc.)
• Easy kth element method and predecessor/successor search
• Range query method with index semantics