Algol 68 sorting
last modified November 13, 2026
Sorting puts the elements of a row into an order. In Algol 68 a row is a
fixed-size collection of values of one mode, and a procedure whose parameter is
REF []INT works on the caller's storage, so it can rearrange the
row in place and return nothing.
This article writes three sorts: insertion sort, quicksort, and merge sort. It counts the comparisons that each one needs, and it shows how a comparison passed as a procedure turns one sort into many.
Insertion sort
The procedure keeps the part of the row before the current position sorted and inserts the next value into it. That value, called the key, is copied out first, and every larger element to its left moves one place to the right. The key then goes into the gap that the shifts have opened.
PROC print row = ([]INT a) VOID:
(
FOR i FROM LWB a TO UPB a DO
IF i > LWB a THEN print(" ") FI;
print(whole(a[i], 0))
OD;
print(newline)
);
PROC insertion sort = (REF []INT a) VOID:
(
FOR i FROM LWB a + 1 TO UPB a DO
INT key := a[i];
INT j := i - 1;
BOOL shifting := j >= LWB a;
WHILE shifting DO
IF a[j] > key THEN
a[j + 1] := a[j];
j -:= 1;
shifting := j >= LWB a
ELSE
shifting := FALSE
FI
OD;
a[j + 1] := key
OD
);
[1:8] INT data := (42, 7, 19, 3, 88, 15, 3, 61);
BEGIN
print row(data);
insertion sort(data);
print row(data)
END
The inner loop has to stop either when the scan reaches the lower bound or when
the element at j is not larger than the key. AND is an
ordinary operator in Algol 68 and does not promise to evaluate its left operand
first, and this implementation evaluates both, so a single test would read
a[0] and fail. The shifting flag makes the bounds
check a separate test that always runs before the element is read.
The output shows the row before and after the call. The two copies of 3 keep their relative order, because an element is only shifted when it is strictly larger than the key.
$ a68g insertion.a68 42 7 19 3 88 15 3 61 3 3 7 15 19 42 61 88
Quicksort
Quicksort picks a pivot, moves every smaller element to the left of it and every larger one to the right, and then sorts the two parts by calling itself. The partition here uses two scans that start at the ends of the range and walk towards each other.
PROC print row = ([]INT a) VOID:
(
FOR i FROM LWB a TO UPB a DO
IF i > LWB a THEN print(" ") FI;
print(whole(a[i], 0))
OD;
print(newline)
);
PROC swap = (REF INT x, y) VOID:
(
INT t := x;
x := y;
y := t
);
PROC quicksort = (REF []INT a, INT lo, hi) VOID:
IF lo < hi THEN
INT pivot := a[(lo + hi) OVER 2];
INT i := lo;
INT j := hi;
WHILE i <= j DO
WHILE a[i] < pivot DO i +:= 1 OD;
WHILE a[j] > pivot DO j -:= 1 OD;
IF i <= j THEN
swap(a[i], a[j]);
i +:= 1;
j -:= 1
FI
OD;
quicksort(a, lo, j);
quicksort(a, i, hi)
FI;
[1:10] INT data := (9, 4, 7, 1, 8, 2, 6, 3, 5, 0);
BEGIN
print row(data);
quicksort(data, LWB data, UPB data);
print row(data)
END
The outer loop ends when the scans have crossed. Each inner loop stops at an
element that is on the wrong side of the pivot, and the swap puts both of them
on the right side. When the scans are done, j ends the left part
and i starts the right one, and the two recursive calls handle
those ranges.
The pivot is copied into a variable before the partition begins, because the swaps move the element that held it. The procedure sorts in place and needs no temporary row, which is why quicksort is the usual choice for a large row that fits in memory.
$ a68g quicksort.a68 9 4 7 1 8 2 6 3 5 0 0 1 2 3 4 5 6 7 8 9
Merge sort
Merge sort divides the range in half, sorts each half, and merges the two sorted halves. The merge copies both halves into temporary rows, then repeatedly takes the smaller of the two front elements and writes it back into the original row.
PROC print row = ([]INT a) VOID:
(
FOR i FROM LWB a TO UPB a DO
IF i > LWB a THEN print(" ") FI;
print(whole(a[i], 0))
OD;
print(newline)
);
PROC merge = (REF []INT a, INT lo, mid, hi) VOID:
(
INT n1 = mid - lo + 1;
INT n2 = hi - mid;
[1:n1] INT left;
[1:n2] INT right;
FOR i TO n1 DO left[i] := a[lo + i - 1] OD;
FOR j TO n2 DO right[j] := a[mid + j] OD;
INT i := 1;
INT j := 1;
INT k := lo;
WHILE i <= n1 AND j <= n2 DO
IF left[i] <= right[j] THEN
a[k] := left[i];
i +:= 1
ELSE
a[k] := right[j];
j +:= 1
FI;
k +:= 1
OD;
WHILE i <= n1 DO a[k] := left[i]; i +:= 1; k +:= 1 OD;
WHILE j <= n2 DO a[k] := right[j]; j +:= 1; k +:= 1 OD
);
PROC merge sort = (REF []INT a, INT lo, hi) VOID:
IF lo < hi THEN
INT mid = (lo + hi) OVER 2;
merge sort(a, lo, mid);
merge sort(a, mid + 1, hi);
merge(a, lo, mid, hi)
FI;
[1:9] INT data := (38, 27, 43, 3, 9, 82, 10, 1, 55);
BEGIN
print row(data);
merge sort(data, LWB data, UPB data);
print row(data)
END
merge declares two rows whose bounds are computed from the values
it receives. Algol 68 evaluates those bounds once, when the block is entered,
so a row of the right size is allocated for each merge. The two loops after the
main loop copy whatever is left in either half; only one of them can run,
because the main loop stops when one half is exhausted.
The merge takes the left element when the two are equal, so equal values keep their original order and the algorithm is stable. The recursion halves the range until a part holds one element, which is already sorted.
$ a68g merge.a68 38 27 43 3 9 82 10 1 55 1 3 9 10 27 38 43 55 82
Counting comparisons
The algorithms differ in how much work they do, and counting comparisons is a
convenient way to see the difference. Every comparison goes through a procedure
less, which increments a counter and then compares its arguments.
The same 200 values, produced by a formula so that the run can be repeated, are
sorted by each algorithm in turn.
INT comparisons := 0;
PROC less = (INT x, y) BOOL:
(
comparisons +:= 1;
x < y
);
PROC insertion sort = (REF []INT a) VOID:
(
FOR i FROM LWB a + 1 TO UPB a DO
INT key := a[i];
INT j := i - 1;
BOOL shifting := j >= LWB a;
WHILE shifting DO
IF less(key, a[j]) THEN
a[j + 1] := a[j];
j -:= 1;
shifting := j >= LWB a
ELSE
shifting := FALSE
FI
OD;
a[j + 1] := key
OD
);
PROC quicksort = (REF []INT a, INT lo, hi) VOID:
IF lo < hi THEN
INT pivot := a[(lo + hi) OVER 2];
INT i := lo;
INT j := hi;
WHILE i <= j DO
WHILE less(a[i], pivot) DO i +:= 1 OD;
WHILE less(pivot, a[j]) DO j -:= 1 OD;
IF i <= j THEN
INT t := a[i];
a[i] := a[j];
a[j] := t;
i +:= 1;
j -:= 1
FI
OD;
quicksort(a, lo, j);
quicksort(a, i, hi)
FI;
PROC merge = (REF []INT a, INT lo, mid, hi) VOID:
(
INT n1 = mid - lo + 1;
INT n2 = hi - mid;
[1:n1] INT left;
[1:n2] INT right;
FOR i TO n1 DO left[i] := a[lo + i - 1] OD;
FOR j TO n2 DO right[j] := a[mid + j] OD;
INT i := 1;
INT j := 1;
INT k := lo;
WHILE i <= n1 AND j <= n2 DO
IF less(right[j], left[i]) THEN
a[k] := right[j];
j +:= 1
ELSE
a[k] := left[i];
i +:= 1
FI;
k +:= 1
OD;
WHILE i <= n1 DO a[k] := left[i]; i +:= 1; k +:= 1 OD;
WHILE j <= n2 DO a[k] := right[j]; j +:= 1; k +:= 1 OD
);
PROC merge sort = (REF []INT a, INT lo, hi) VOID:
IF lo < hi THEN
INT mid = (lo + hi) OVER 2;
merge sort(a, lo, mid);
merge sort(a, mid + 1, hi);
merge(a, lo, mid, hi)
FI;
INT n = 200;
[1:n] INT data;
[1:n] INT work;
BEGIN
INT seed := 7;
FOR i TO n DO
seed := (seed * 75 + 74) MOD 65537;
data[i] := seed MOD 1000
OD;
work := data;
comparisons := 0;
insertion sort(work);
print(("insertion ", whole(comparisons, 0), newline));
work := data;
comparisons := 0;
quicksort(work, 1, n);
print(("quicksort ", whole(comparisons, 0), newline));
work := data;
comparisons := 0;
merge sort(work, 1, n);
print(("merge sort ", whole(comparisons, 0), newline))
END
Insertion sort needs about n²/4 comparisons on random data, which is 9971 for 200 values. Quicksort needs about n log n, here 1821, and merge sort 1285. The exact numbers depend on the data and on the choice of pivot, but the ratio grows with the size of the row: at a thousand elements insertion sort makes roughly twenty times as many comparisons as the other two.
The counter is a variable declared outside the procedures, and every call to
less changes it. That is a simple way to instrument an algorithm,
though a program that ran two sorts at the same time would need a semaphore
around the counter, as the parallel
clause article explains.
$ a68g counting.a68 insertion 9971 quicksort 1821 merge sort 1285
Comparators as procedures
An order is a rule that says whether one value comes before another. Algol 68
has procedure values, so the rule can be a parameter.
MODE CMP = PROC (INT, INT) INT declares a mode whose values are
procedures that take two integers and answer a negative number, zero, or a
positive number.
MODE CMP = PROC (INT, INT) INT;
PROC ascending = (INT x, y) INT:
IF x < y THEN -1 ELIF x > y THEN 1 ELSE 0 FI;
PROC descending = (INT x, y) INT:
IF x > y THEN -1 ELIF x < y THEN 1 ELSE 0 FI;
PROC by last digit = (INT x, y) INT:
IF x MOD 10 < y MOD 10 THEN -1
ELIF x MOD 10 > y MOD 10 THEN 1
ELSE 0
FI;
PROC sort by = (REF []INT a, CMP cmp) VOID:
(
FOR i FROM LWB a + 1 TO UPB a DO
INT key := a[i];
INT j := i - 1;
BOOL shifting := j >= LWB a;
WHILE shifting DO
IF cmp(key, a[j]) < 0 THEN
a[j + 1] := a[j];
j -:= 1;
shifting := j >= LWB a
ELSE
shifting := FALSE
FI
OD;
a[j + 1] := key
OD
);
PROC print row = ([]INT a) VOID:
(
FOR i FROM LWB a TO UPB a DO
IF i > LWB a THEN print(" ") FI;
print(whole(a[i], 0))
OD;
print(newline)
);
[1:7] INT data := (42, 7, 19, 3, 88, 15, 61);
[1:7] INT work;
BEGIN
work := data;
sort by(work, ascending);
print("ascending ");
print row(work);
work := data;
sort by(work, descending);
print("descending ");
print row(work);
work := data;
sort by(work, by last digit);
print("last digit ");
print row(work)
END
sort by is the insertion sort of the first section with one
change: the test a[j] > key became cmp(key, a[j]) < 0.
The three comparators order the same data in three ways, and the last one looks
only at the final digit, so values that end in the same digit keep their
relative order.
Because cmp runs once per comparison, a comparator can also count
calls, write a trace, or compare a field of a structure. Passing it as a
parameter keeps the sorting code in one place instead of one copy per order,
which is the same reason the comparison counter of the previous section was
easy to add.
$ a68g comparators.a68 ascending 3 7 15 19 42 61 88 descending 88 61 42 19 15 7 3 last digit 61 42 3 15 7 88 19
Choosing a sort
The standard prelude of Algol 68 has no sorting procedure, so a program brings its own. Insertion sort is the shortest to write and the fastest for rows of a few dozen elements. Quicksort is the usual general-purpose choice, because it sorts in place and its average cost grows as n log n. Merge sort costs extra memory for the temporary rows but keeps equal elements in order and has no bad case.
All three work on a fixed row and cannot change its bounds. A program that collects values of unknown number needs a flexible row, which the flexible rows article describes, and the sorted row is what makes the binary search of the searching article possible.
Next steps
The rows article explains the bounds and slices
that the sorts rely on, and procedures
covers the REF parameters and procedure values used here. The
searching article takes a sorted row and
finds a value in it, and
linked lists shows a structure that keeps
its values in order without moving any of them.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we have sorted rows with insertion sort, quicksort, and merge sort, counted the comparisons that each one needs, and passed the comparison itself as a procedure so that one sort serves several orders.
Author
List all Algol 68 tutorials.