Extend the data linked list node type by a real number field and compare that field through an Oberon type guard.
TYPE RealNode = RECORD (Node) value: REAL END;
     RealTail = POINTER TO RealNode;

PROCEDURE RealLess(p, q: Tail): BOOLEAN;
BEGIN
  RETURN p(RealTail).value < q(RealTail).value
END RealLess;
Construct the data chain from RealTail nodes, retain the ordinary Header for its header, set its count correctly, and call
MergeSort(RealLess, p)
Only data nodes reach RealLess, so the header needs no real-valued field. Its precondition is that every data node has the RealNode extension. With ordinary real numbers, the comparison supplies a total order; machine values such as NaN must be excluded if the machine floating-point number type admits them.
The abstract state is a finite multiset of ordered values, initially empty. Multiplicity matters: deleting the minimum removes one occurrence, not every equal occurrence. Assume a consistent total order on T.
trait PriorityQueue[T] {
  // Pre: true. Post: Q' is the empty multiset.
  def clear(): Unit

  // Pre: true. Post: Q' = Q with one additional occurrence of x.
  def insert(x: T): Unit

  // Pre: Q is nonempty.
  // Post: result is a minimum of Q;
  //       Q' is Q with exactly one occurrence of result removed.
  def delMin(): T

  // Pre: true. Post: result iff Q is empty, and Q' = Q.
  def isEmpty(): Boolean
}
This abstract data type places no fixed-capacity bound on insertion. The only operation requiring a nonempty collection is delMin. The representation must preserve duplicates even if it uses a data structure commonly associated with sets.
A compatible Ord instance supplies a total order, so use comparison sort to put equal values together in time and then group adjacent equals in linear time. To preserve the first-occurrence group ordering of part (f), first tag every element with its original index and stable sorting by value. Group the sorted records by value; stability preserves their internal input order. Each group's first record carries its smallest original index. Sort the groups by that index and finally remove the tags. The second sort has at most records, so the total remains time and storage. Merely returning the value-sorted groups could reorder the classes, so the index step matters when preserving the exact earlier convention. The stronger interface evades the equality-only lower bound by permitting order comparisons.
For the pointwise order on real polynomials, proves reflexivity. Two opposite inequalities imply for every real ; the polynomials are therefore equal, proving the antisymmetric relation axiom. Chaining the inequalities at every proves transitivity.
To disprove total order, take and . The inequality fails at , whereas fails at . The order is partial but non-total.
For the product order, reflexivity follows from in every coordinate. If and , the antisymmetric relation axiom for the usual real order gives for every , hence . If , transitivity in each coordinate gives , hence . Thus this is a partial order.
For , the vectors and are incomparable: each has a coordinate larger than the corresponding coordinate of the other. It is not a total order for . The dimension qualification matters: for this is the usual total order on , so the printed non-totality claim needs the implicit assumption .
Pointwise order 2026-10-31
Given a partially ordered set and a set , the pointwise order on the function space of functions compares their values at every argument. It is a partial order: reflexivity and transitivity hold at every argument, and antisymmetry follows because two functions equal at every argument are equal. Even if has a total order, this function space need not: the two functions on with values and are incomparable when .
Pointwise order on real polynomials Created 2026-10-25 Updated 2026-10-31
This is a partial order: the real inequalities supply reflexivity and transitivity, while inequalities in both directions give equality of the polynomials as functions. It is not a total order, since the polynomials and are incomparable on all of . Restricting the test domain can change the relation; testing only at finitely many points need not distinguish different polynomials.
Priority queue 2026-10-13
A priority queue stores items with comparable priority keys and supports insertion, inspection of a best-priority item, and removal of a best-priority item. Here we use the minimum convention: keys have a total order, and smaller means earlier. The operation peek returns a stored item of minimum priority without removing it; extract-min removes and returns such an item. Both require a nonempty priority queue, or an explicitly specified empty-case result. A maximum-oriented priority queue reverses the choice.
For the requests , peek returns Bo and leaves all three requests stored. extract-min returns Bo and leaves Ada and Cy; another peek returns Cy. Inserting now makes Dee the next request selected. This changing collection need not be a sorted array: only the next choice must be available.
Distinct items may share a priority. Inserting alongside permits either item to be removed first. A priority queue does not inherently promise arrival order on ties. If that policy matters, compare priority first and a unique increasing arrival number second; the resulting total order makes earlier arrivals win equal-priority ties. This is analogous to the motivation for stable sorting, but it is an extra policy for the priority queue.
The interface specifies behavior; the data structure determines costs. A binary heap implements a priority queue with constant-time peek and logarithmic-time insertion and extract-min, under the cost assumptions below. Scheduling by urgency or by the time of the next event needs exactly this repeated next-item selection. MIT's notes use these applications to motivate the priority queue interface.[ref]
Product order 2026-10-14
The product order on a Cartesian product of partially ordered sets compares every coordinate separately. Points that improve one coordinate and worsen another are incomparable. It is generally a partial order, not a total order.
Radix sort key encoding 2026-10-18
An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position , a one-unit numerical digit difference contributes , while all lower positions together contribute at most
This geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.
For signed integers in a known integer interval , encode and choose with . This order-preserving function is also injective: exactly when . For , the four-bit encodings of are after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.
For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use , let every string have length at most three, encode as one and as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings encode as in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode as and as , reversing . Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.
Figure 1.
Stable ties preserve lower digits; suitable encodings preserve the intended order
. Original counterexample above: reversing a tens tie destroys the units order and a later stable hundreds pass cannot repair it. Below: signed integer offsets and a reserved end marker for bounded strings produce increasing fixed-width encodings. All entries are exact constructed examples. Details.
Real number Created 2026-09-24 Updated 2026-11-05
A real number is an element of the complete ordered field . This includes integers, rational numbers such as , and irrational numbers such as . The number line represents each real number by a point, and the total order distinguishes which of two different points is larger.
The field operations permit addition, subtraction, multiplication and division by nonzero real numbers. Completeness adds the least-upper-bound property: every nonempty set of real numbers that is bounded above has a supremum in . For example, the positive real numbers whose squares are less than two have supremum . That supremum is not a rational number, illustrating why the rational numbers alone leave a gap.
The density of the rational numbers means every real number can be approximated arbitrarily closely by rational numbers. Constructions through Cauchy sequences or Dedekind cuts make those approximations into a precise description of .
Sequential consistency Created 2026-10-14 Updated 2026-10-31
Execution behaves as if steps occurred in one total order preserving each participant's program order; reads observe the latest preceding writes in that order. This is the definition given in the 1979 paper How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, printed p. 690. It permits many thread interleavings, including the lost update under mutual exclusion; ordering individual accesses does not combine them into one atomic operation.
Sorted array 2026-10-13
An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.
For example, is a sorted array of integers. Inserting at index gives : with spare capacity, first shift one slot right. Appending 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 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 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.
Sortedness 2026-10-13
For an output sequence of length , sortedness means
under the chosen total order on sort keys. Its transitivity also gives whenever . An empty sequence and a one-entry sequence satisfy sortedness without any adjacent comparison. For longer sequences, checking adjacent pairs suffices; checking only the first and last sort keys does not. For example, passes an endpoint comparison but fails sortedness at . Sortedness alone says nothing about which input entries survived.
Sorting algorithm 2026-10-13
A sorting algorithm rearranges a finite sequence into nondecreasing order under a chosen total order on its keys. Its output must contain every input entry exactly once, including repetitions: producing ordered values is insufficient if entries are lost. Merge sort is one such algorithm; stable sorting adds a requirement about equal keys.
Sorting creates reusable structure: equal sort keys become adjacent, and a sorted array supports binary search. However, an algorithm correctness check must establish both sortedness and sorting permutation preservation. Replacing every entry by the smallest key can produce ordered keys while destroying the original data. Stable sorting imposes a third condition when equal sort keys occur: retain their arrival order.
For example, take complete sorting records , with the first component as the sort key and the letter as associated data. A correct output is . The sort keys are ordered, every complete sorting record remains, and the equal-key pairs keep before and before . The output satisfies sortedness and sorting permutation preservation, but fails stable sorting. The output has the right multiset of sort keys but loses and duplicates ; it fails sorting permutation preservation of complete sorting records.
To express stable sorting precisely, label every input occurrence by its original position, even when two complete sorting records have identical contents. Let be the output position of the occurrence originally at position . Besides sortedness and sorting permutation preservation, require
Here is the sort key function. Sorting by the pair under lexicographic order gives the same order as stable sorting by : the original position breaks ties without discarding associated data. For a two-field ordering, first apply stable sorting by the secondary sort key, then apply stable sorting by the primary sort key. The second pass retains the secondary order within each group of equal primary sort keys. For instance, first becomes by letter, then by number.
Sort key Created 2026-10-13 Updated 2026-10-20
A sort key is the value extracted from a complete entry to determine its ordering. Model extraction as a function into a total order; compare and , while moving the complete entries. Ordering sorting records by an age field does not also compare their names. Repeated sort keys are allowed, so this induces equal-key groups even when the complete sorting records differ. Keep the sort key function and the comparison rule fixed throughout a sort; inconsistent comparisons need not admit any sorted result.
Every partial order has a total order extension. Apply Zorn's lemma to extensions ordered by inclusion: the union of a chain is a partial order. If a maximal extension leaves two elements incomparable, adjoining one comparison and taking its transitive closure of a relation creates no cycle, contradicting maximality. Quotienting a preorder by its indifference relation and lifting a total order gives a complete weak-order extension preserving its strict part.