For finite acyclic chains, define the abstraction function recursively by
(1)
Here the list contains linked list nodes themselves. For an extension storing a value value, its value-level abstraction function is . Finiteness and absence of a graph cycle ensure that these recursive definitions terminate. A dummy header node is excluded by applying to its tail.
A dummy header node gives the first actual linked list node a predecessor, just like every other element. Linked-list deletion and insertion at the front can therefore update a predecessor's tail with the same code used in the middle. An empty linked list is represented by a header whose tail is NIL.
(1)
The representation invariant is
(1)
Every reachable non-NIL pointer designates an allocated linked list node of the appropriate extension type. The header is not a data element. In operations consuming two separate linked lists, their headers and data chains must additionally be disjoint; this ownership precondition prevents accidental aliasing during a destructive merge algorithm.
Reuse p as q's header and allocate one new header for r. Cut after data elements, allowing .
PROCEDURE Split(p: List; VAR q, r: List);
VAR n, k, i: INTEGER; last: Tail;
BEGIN
  n := p.count; k := n DIV 2;
  q := p; NEW(r);
  last := q;
  FOR i := 1 TO k DO last := last.tail END;
  r.tail := last.tail; last.tail := NIL;
  q.count := k; r.count := n-k
END Split;
The traversal starts at the dummy header node, so after steps last precedes the suffix assigned to r. Cutting that link produces two finite disjoint linked lists. Their concatenated abstraction function is the original list, with order preserved, and
(1)
Both empty and singleton inputs work without special traversal cases. The time complexity is and only one header is allocated.
Assume less is a lawful strict comparison, for example a strict weak order, and the two input linked lists are disjoint and sorted by it. Allocate a result header and move existing data linked list nodes; do not copy their values.
PROCEDURE Merge(less: LESS; q, r: List; VAR p: List);
VAR result: List; last, a, b: Tail;
BEGIN
  NEW(result); result.count := q.count + r.count;
  result.tail := NIL; last := result;
  a := q.tail; b := r.tail;
  WHILE (a # NIL) & (b # NIL) DO
    IF less(b,a) THEN
      last.tail := b; b := b.tail
    ELSE
      last.tail := a; a := a.tail
    END;
    last := last.tail
  END;
  IF a # NIL THEN last.tail := a ELSE last.tail := b END;
  q.tail := NIL; q.count := 0;
  r.tail := NIL; r.count := 0;
  p := result
END Merge;
The loop invariant says that the segment from result.tail through last is a sorted prefix of the desired merge algorithm, containing exactly the nodes already removed from the two unread chains. Every element of this prefix is no greater than either unread head. Choosing the smaller unread head maintains this property; choosing from q on a tie also gives stable sorting.
At exit, at most one unread chain is nonempty, and its sorted suffix can be attached as a whole. Each original data linked list node occurs exactly once in the result, and its saved count is correct. Clearing the consumed headers prevents them from claiming ownership of the result's nodes.
(1)
Use merge sort, stopping before an empty or singleton linked list would be split.
PROCEDURE MergeSort(less: LESS; VAR p: List);
VAR q, r: List;
BEGIN
  IF p.count > 1 THEN
    Split(p, q, r);
    MergeSort(less, q); MergeSort(less, r);
    Merge(less, q, r, p)
  END
END MergeSort;
By induction on the length, each recursive call returns a sorted permutation of its input. Part (d) makes both child lengths smaller than the parent whenever the parent length exceeds one; part (e) combines the sorted children. No data linked list nodes are newly allocated or lost. Unreachable headers may be reclaimed by garbage collection.
At each level the total splitting and merge algorithm work is linear; approximately equal halves give logarithmic depth. Consequently
(1)
There are header allocations over the whole execution; those allocations should not be confused with the logarithmic call stack bound.
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.
(1)

Ancestors (10)

  1. Imperative programming
  2. 2015
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version