Sorted Array¶
A sorted array keeps comparable keys in contiguous index order, enabling binary-search lookup and contiguous ranges while making middle updates costly.
Core Idea¶
A sorted array combines two properties: elements occupy indexable adjacent positions, and their keys follow a consistent comparison order. Because the key at the middle index divides the possible locations of a query key, binary search can eliminate half the remaining range at each comparison. Two boundary searches also locate a contiguous run of values in an interval. The cost of maintaining the invariant is asymmetric: finding an insertion point is logarithmic, but making room there in a compact array moves later elements, so middle insertion is linear. Python's bisect documentation explicitly warns that its insort operation is O(n) despite the logarithmic search step.[1][2]
This is a data structure, not a sorting algorithm. GNU gprof provides an implemented instance: it constructs a contiguous symbol table, sorts it by address, then binary-searches it for address lookup. MIT's one-dimensional range-search lecture gives another: sort scalar points, binary-search both interval endpoints, then output the points between them.[3][2]
Structural Signature¶
Sig role-phrases:
- Keyed elements: records have keys under one comparison rule.
- Contiguous indexable array: middle and neighboring positions are reachable by index without traversing preceding elements.
- Order invariant: keys do not decrease as indices advance.
- Search or interval operation: one or two binary searches find a key or boundary; an adjacent scan reports a range.
- Update workload: frequency of middle insertions/deletions decides whether shifting costs outweigh read gains.[2][1]
Condensed: indexable contiguous storage + monotone keys → binary-search boundaries and ordered scans, at linear middle-update cost.
What It Is Not¶
A sorted linked list has monotone keys but no constant-time midpoint indexing; it does not inherit array binary-search complexity. An unsorted array has indexing but no order invariant to justify discarding half the search space. A balanced search tree also supports ordered queries but stores a navigable branching structure and handles dynamic updates differently. An SST file in a storage engine has sorted records, yet its block/index/disk organization is not automatically identical to a single RAM array. Nor is a sorted array always preferable to a hash table: if only exact-key lookup matters and key order is irrelevant, the comparison changes.[2][1]
Scope of Application¶
The structure is attractive when a collection is built or sorted once and searched many times, or when ordered range reporting matters. In gprof, a contiguous table of symbols is built, sorted by memory address and queried by binary search during profile analysis. This use makes the cost of a one-time sort plausible relative to repeated lookup. It does not establish that every compiler keyword table or symbol table uses this representation.[3]
For one-dimensional points, MIT's lecture gives an interval query [a,b]: binary-search for the lower and upper boundaries, then return the intervening k points. Its time is O(log n+k)—not merely O(log n), because reporting k values requires output work. The same lecture contrasts sorted arrays with dynamic structures when insertions and deletions become important.[2]
Clarity¶
“Sorted” is a maintained condition on the array, not a property of the query. If the keys are [2,5,5,9,13], a search for 5 may stop at either duplicate; a range query needs lower and upper boundary conventions so it returns both. To insert 7, binary search can find index 3, but 9 and 13 must shift right in a compact array. One should state whether duplicates are allowed, which comparator defines order, and whether a query seeks any match, the first match, an insertion point, or all values in an interval.[1]
Manages Complexity¶
The structure turns a potentially large set of comparisons into indexed arithmetic over a monotone sequence. For a static lookup table, the mental model is simple: sort, keep the invariant, compare at a midpoint, shrink the interval. For range search, it separates boundary location from output enumeration. Yet the simple representation exposes a workload tradeoff: mutations can demand copying or shifting an entire suffix. When workload changes from mostly reads to frequent updates, an ordered tree or batched rebuild may be preferable; which is faster depends on actual sizes, memory hierarchy and implementation, not on asymptotic notation alone.[2][1]
Abstract Reasoning¶
Let A[0..n-1] satisfy A[i].key ≤ A[i+1].key. For a target q, inspect A[m] at a midpoint. If A[m].key < q, every index at or below m can be excluded from a lower-bound search. If A[m].key ≥ q, the lower bound lies at m or to its left. Repeating this halves the candidate interval, yielding O(log n) comparisons. For [a,b], find the first index with key at least a and the first index with key greater than b; exactly the slice between them is reported. The proof relies on both the order invariant and indexed midpoint access.[2][1]
Insertion demonstrates the inverse cost. Even after a logarithmic lower-bound search, putting a new record at a middle index in a contiguous array requires moving each later record one position. In the worst case, that suffix is proportional to n. The invariant that makes reads quick is the invariant that must be restored after writes.[1]
Knowledge Transfer¶
The gprof table and the one-dimensional point array share indexed order and boundary search despite very different key meanings—addresses versus geometric coordinates. The gprof operation finds a symbol associated with an address; the point operation locates an interval and reports k points. What transfers is the representation-and-search logic, not the precise comparison rule or output. A proposed transfer to an immutable disk run needs a new analysis of block access and indexing; a proposed transfer to a heavily mutable in-memory set needs an update-cost comparison.[3][2]
Examples¶
GNU gprof symbol-address table¶
The GNU gprof manual describes a Sym array created at a required size, sorted after construction, and searched by address through sym_lookup using binary search. This is not a hypothetical “compiler table”: the implementer explicitly identifies contiguous storage and the search routine. The build/finalize phase bears the sorting work before subsequent symbol lookups.[3]
Mapped back: Sym records are keyed elements; the table is a contiguous array; address order is maintained after sorting; sym_lookup performs binary search for address-associated symbols; its build-then-read pattern makes repeated middle insertion unnecessary in the described phase.
One-dimensional interval search¶
MIT's range-search lecture starts with scalar points x_i, keeps them in a sorted array, and answers an interval query by binary-searching both endpoints. If k points lie inside, output takes O(log n+k). The same source notes that sorted arrays are inefficient for insertion and deletion, motivating another structure for dynamic queries.[2]
Mapped back: scalar coordinates are keyed elements; the points occupy an indexed array; ascending coordinate order is the invariant; two binary searches find interval bounds and an adjacent scan emits the k points; a dynamic update-heavy workload would pay shifts and change the data-structure choice.
Structural Tensions¶
Read speed versus update movement. The maintained order allows logarithmic position finding, but inserting or deleting at a middle position in a compact array shifts up to linearly many entries. Neither “always fast” nor “always slow” describes the structure. Diagnostic: how many searches or range queries occur per insertion/deletion, and can updates be batched?[2][1]
Locating an interval boundary and enumerating its k members are sequential work components, not competing aims: an output-producing range query costs at least the output size even after a logarithmic boundary search. Specify whether the task asks for a boundary, a count or every element before quoting its running time.[2]
Structural–Framed Character¶
This entry is overwhelmingly structural: contiguous positions, a comparator, monotone order and midpoint access determine its performance. The evaluative part is engineering choice—whether the workload favors inexpensive searches over costly updates—not a value claim embedded in the keys. Human practice selects comparator, duplicate convention and update policy; software institutions document specific uses, but do not create the algorithmic relation. Its vocabulary travels literally from profiler symbol addresses to geometric coordinates because the same array/order/search roles recur. Calling a merely alphabetized linked list a sorted array would import the term while omitting the indexable-storage mechanism. Its character: an ordered contiguous representation with a provable search/update asymmetry.
Structural Core vs. Domain Accent¶
The skeletal relation is ordered indexed representation → interval elimination for search → shifts to preserve order on mutation. Memory addresses and 1D point coordinates are accents: different keys in the same mechanism. The domain-bound mechanism remains array indexing, comparison order and element movement; it fails the prime bar because those implementation commitments define the identity. Live Data Structure is the strict arrangement-for-use parent. A broader future prime about trading maintenance cost for query speed would need unlike-domain evidence and should not inherit this entry's complexity bounds by analogy.
Instantiates / Related Primes¶
This entry is a kind of Data Structure.
Live Data Structure is the strict parent: the sorted array is a concrete arrangement that privileges indexed and ordered search while making middle updates costly. No exact duplicate sorted-array V2 identity was found. A sorting algorithm produces order but is not itself the resulting indexed data structure; tree sort is an algorithmic neighbor, not a parent edge.
Relationships to Other Abstractions¶
Current abstraction Sorted Array Domain-specific
Parents (1) — more general patterns this builds on
-
Sorted Array is a kind of Data Structure Prime
A sorted array is a concrete data structure combining indexable storage with maintained key order.Every admitted instance arranges elements in indexed array positions under monotone comparison order, enabling binary/range search while imposing movement cost on middle updates. Those layout and operation tradeoffs specialize the live Data Structure genus.
Hierarchy path (1) — routes to 1 parentless root
- Sorted Array → Data Structure → Trade-offs → Constraint
Neighborhood in Abstraction Space¶
Sorted Array sits in a moderately populated region (59th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Storage & Lookup Data Structures (21 abstractions)
Nearest neighbors
- K-d Tree — 0.87
- Multimap — 0.85
- Parallel Array — 0.85
- Queap — 0.85
- Queue (FIFO Abstract Data Type) — 0.84
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
Binary search is an operation enabled by the invariant, not the stored collection. A sorted linked list lacks fast midpoint indexing. A B-tree or SST-based storage engine has its own block/index costs. The simple array's O(log n) search does not make an insort update logarithmic.[1]
References¶
[1] Python Software Foundation, bisect documentation, performance notes and sorted-list searches. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i
[2] MIT OpenCourseWare, 6.046J Lecture 9: Orthogonal Range Searching and Range Trees, one-dimensional case. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k
[3] GNU Binutils, gprof manual, symbol-table construction and sym_lookup. registry ↩a ↩b ↩c ↩d