Return the exclusive endpoint of the maximal initial run:The loop invariant is and is nondecreasing. An unsuccessful adjacent-order test extends the run by one; a strict descent at prevents any extension across it. If , the whole segment is a run. The loop variant is .For a run of length , the running time is , including at most one failed extension test; an empty segment takes .
PROCEDURE Run(a, b: INTEGER): INTEGER;
VAR c: INTEGER;
BEGIN
IF a = b THEN RETURN b END;
c := a+1;
WHILE c < b DO
IF u[c-1] > u[c] THEN RETURN c END;
c := c+1
END;
RETURN c
END Run;Use a merge algorithm with one unread index in each run. Here Let denote the original two runs. The first loop invariant says and is the sorted merge of and ; moreover each emitted value is at most every unread value. Choosing the smaller head preserves that condition. Equal heads are taken from the first run, giving stable sorting within this merge. The loop variant is .
u is the module's array; the destination is disjoint from the source and lies within the array bounds:PROCEDURE Merge(a, b, c, d: INTEGER);
VAR i, j, k: INTEGER;
BEGIN
i := a; j := b; k := d;
WHILE (i < b) & (j < c) DO
IF u[i] <= u[j] THEN
u[k] := u[i]; i := i+1
ELSE
u[k] := u[j]; j := j+1
END;
k := k+1
END;
WHILE i < b DO
u[k] := u[i]; i := i+1; k := k+1
END;
WHILE j < c DO
u[k] := u[j]; j := j+1; k := k+1
END
END Merge;For each copying loop, the output remains the sorted merge of the consumed prefixes, at least one source run is exhausted, and only the indicated suffix remains. The respective loop variants are and . At exit both source runs are exhausted:The destination's multiset is the sum of the two source multisets.
Treat the live array segment as a FIFO queue of runs. Remove its first two runs, append their merged result, and repeat:Compute both run boundaries before writing the destination, which starts at the old
PROCEDURE Sort(a, b: INTEGER; VAR c, d: INTEGER);
VAR x, y, z: INTEGER;
BEGIN
c := a; d := b;
WHILE c < d DO
x := Run(c, d);
IF x = d THEN RETURN END;
y := Run(x, d);
z := y-c;
Merge(c, x, y, d);
c := y;
d := d+z
END
END Sort;d. The untouched suffix is followed by the new merged run. The endpoints returned in c,d always describe the live sequence; obsolete values before c are ignored. As allowed, assume enough destination capacity.For example, becomes the live sequence , then . The first merge combines and , and the second combines and .
Let be the original sequence and . The loop invariant isHere denotes the multiset of entries. The capacity condition uses the question's assumption of sufficient space. Removing two runs of combined length and appending their merge preserves the length and multiset. It also leaves all live values in one contiguous segment.
For a nonempty live sequence, let be its number of maximal initial runs obtained by repeatedly cutting at strict adjacent descents. The loop variant is . If
x = d, there is one run and the procedure returns a sorted permutation. Otherwise the iteration removes two runs and appends one; it cannot create a new descent inside that appended run. The appended run may join the last old run, further reducing , so decreases by at least one. There are at most merges.For , the loop is skipped and the empty segment is already sorted. No global stability claim is needed: moving a merged run behind other runs can change the order of equal-labelled occurrences.Let be the total length of the two runs in merge . Because destinations are always appended beyond the old endpoint, the exact space consumption isA simple valid bound is , using at most merges. The FIFO queue schedule permits the sharper asymptotic boundTo prove the upper bound, group merges into rounds. Mark the old end of the live segment, and finish a round when all runs present at its start have been consumed. If there are such runs, at most merges occur. Only the last merge can pair one remaining old run with an already appended run. Consequently at most runs remain; coalescence can only reduce this number. Every start-of-round entry is merged once, and entries in the one possible already appended run are merged at most once more. A round writes at most entries. After at most rounds there is one run, giving for .
For a matching family, let and use repetitions of . Each initial run has length two. Every merged run still starts at zero and ends at one, so adjacent runs never coalesce. In each of the complete merging levels exactly entries are written. Henceon this family. For an already sorted input, no merge occurs and .
If the merge algorithm from part (b) is retained with a disjoint destination, use a circular buffer of cells. Represent the live segment by its start modulo and its length . The other cells are free; the next merge needs at most output cells. Appending its output and advancing the live start releases exactly as many obsolete source cells. Logical run boundaries and copying indices are reduced modulo . The final sorted sequence may wrap, in which case an array rotation makes it contiguous. ThusThis is also the worst-case requirement if all source cells must be retained until a whole disjoint merge has been written: the final two runs can have combined length .
Under the question's literal wording, however, no running time requirement or disjoint-output restriction is imposed on the modified implementation. The absolute smallest array isTo achieve this, replace the disjoint-output merge by an in-place merge: compare the next unread values of the two adjacent runs; when the second is smaller, save it in one scalar, shift the intervening first-run block right by one, and insert it before that block. This is a sorted merge using no extra array. Its loop invariant is that the finished prefix is the sorted merge of the consumed portions and the two remaining runs stay sorted. Each step consumes one value, proving termination.
After merging the first two runs in place, rotate the merged prefix behind the untouched suffix. Three array reversals implement this rotation with one scalar: reverse the merged prefix, reverse the suffix, then reverse the whole segment. The resulting live sequence is exactly the one produced in part (c). Repeat the same run schedule until sorted. The shift and reversal loops respectively preserve the copied block and exchanged end pairs; their loop variants are the unshifted length and half the unreversed length. The modification can be substantially slower, but preserves the loop invariant and decreasing run count from part (d). Fewer than cells cannot even hold the specified input entries. Thus is the natural circular-workspace answer for the original merge primitive, while is attainable when minimizing storage over all implementations allowed by the stated time-free specification.
Articles by others on the same topic
There are currently no matching articles.