= Sorted array
{title2=$A_0\leq A_1\leq\cdots\leq 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.
Back to article page
