Sorting algorithms/Merge sort: Difference between revisions
m
→{{header|Component Pascal}}: Remove superfluous comments
m (→{{header|Component Pascal}}: change "StdLog" to "Out") |
m (→{{header|Component Pascal}}: Remove superfluous comments) |
||
Line 2,897:
(* Return TRUE if `front` comes before `rear` in the sorted order, FALSE otherwise *)
(* For the sort to be stable `front` comes before `rear` if they are equal *)
PROCEDURE (IN t: Template)
(* Return the next element in the list after `s` *)
PROCEDURE (IN t: Template)
(* Update the next pointer of `s` to the value of `next` - Return the modified `s` *)
Line 2,909:
VAR n: INTEGER;
BEGIN
n := 0;
WHILE s # NIL DO
INC(n);
s := t.Suc(s)
END;
RETURN n
END Length;
Line 2,922:
IF front = NIL THEN RETURN rear END;
IF rear = NIL THEN RETURN front END;
IF t.
RETURN t.Set(front, t.Merge(t.
ELSE
RETURN t.Set(rear, t.Merge(front, t.
END
END Merge;
Line 2,939:
BEGIN
IF n = 1 THEN (* base case: if n = 1, return the head of `s` *)
h := s; s := t.
END;
(* Divide the first n elements of the list into two sorted halves *)
k := n DIV 2;
front := TakeSort(k,
rear := TakeSort(n - k, s);
RETURN t.Merge(front, rear) (* Merge and return the halves *)
Line 2,949:
BEGIN
IF s = NIL THEN RETURN
(* Calculate the length of the list and call TakeSort *)
RETURN TakeSort(t.Length(s), s) (* Return the sorted list *)
| |||