Sorted array ($A_0\le A_1\le \cdots \le A_{n-1}$)

An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.

For example, $(2,5,5,9)$ is a sorted array of integers. Inserting $7$ at index $3$ gives $(2,5,5,7,9)$: with spare capacity, first shift $9$ one slot right. Appending $7$ would violate the sorted array property. Updating an entry also requires preserving the total order, or removing and reinserting it in a suitable position.

The useful combination is order plus direct indexed access: binary search eliminates a whole interval of candidates at each comparison, giving $O(\log n)$ search time complexity under constant-cost comparisons and the array cost model. A sorted array is therefore attractive for many lookups between changes, while keeping it sorted can still require $O(n)$ shifting work per insertion. A sorted linked list has the ordering information but does not supply the same constant-cost access to a middle index.