# Category talk:ALGOL 68-sort

### Source code

```# sort.incl.a68: sorting related modes, operators, etc.                       #

# mode to hold the array bounds for sorting a subset of the array         #
MODE ELEMENTS = STRUCT( INT low, high );

# swaps the values of a and b                                             #
PRIO =:= = 9;
OP   =:= = ( REF INT    a, b )REF INT:    BEGIN INT    t := b; b := a; a := t END;
OP   =:= = ( REF REAL   a, b )REF REAL:   BEGIN REAL   t := b; b := a; a := t END;
OP   =:= = ( REF STRING a, b )REF STRING: BEGIN STRING t := b; b := a; a := t END;

# in-place quick sort a[ low OF bounds : high OF bounds ]                 #
PRIO QUICKSORT = 9;
OP   QUICKSORT = ( REF[]INT a, ELEMENTS bounds )REF[]INT:
IF INT lb = low OF bounds, ub = high OF bounds;
ub <= lb
THEN a                         # at most 1 element - no need to sort #
ELSE                           # more than one element, so must sort #
INT left  := lb;
INT right := ub;
# choosing the middle element of the array as the pivot           #
INT pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
WHILE
WHILE IF left  <= ub THEN a[ left  ] < pivot ELSE FALSE FI
DO
left  +:= 1
OD;
WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI
DO
right -:= 1
OD;
left <= right
DO
a[ left  ] =:= a[ right ];
left       +:= 1;
right      -:= 1
OD;
a QUICKSORT ELEMENTS( lb,   right );
a QUICKSORT ELEMENTS( left, ub    )
FI # QUICKSORT # ;
OP   QUICKSORT = ( REF[]REAL a, ELEMENTS bounds )REF[]REAL:
IF INT lb = low OF bounds, ub = high OF bounds;
ub <= lb
THEN a                         # at most 1 element - no need to sort #
ELSE                           # more than one element, so must sort #
INT left   := lb;
INT right  := ub;
# choosing the middle element of the array as the pivot           #
REAL pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
WHILE
WHILE IF left  <= ub THEN a[ left  ] < pivot ELSE FALSE FI
DO
left  +:= 1
OD;
WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI
DO
right -:= 1
OD;
left <= right
DO
a[ left  ] =:= a[ right ];
left       +:= 1;
right      -:= 1
OD;
a QUICKSORT ELEMENTS( lb,   right );
a QUICKSORT ELEMENTS( left, ub    );
a
FI # QUICKSORT # ;
OP   QUICKSORT = ( REF[]STRING a, ELEMENTS bounds )REF[]STRING:
IF INT lb = low OF bounds, ub = high OF bounds;
ub <= lb
THEN a                         # at most 1 element - no need to sort #
ELSE                           # more than one element, so must sort #
INT left  := lb;
INT right := ub;
# choosing the middle element of the array as the pivot           #
STRING pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
WHILE
WHILE IF left  <= ub THEN a[ left  ] < pivot ELSE FALSE FI
DO
left  +:= 1
OD;
WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI
DO
right -:= 1
OD;
left <= right
DO
a[ left  ] =:= a[ right ];
left       +:= 1;
right      -:= 1
OD;
a QUICKSORT ELEMENTS( lb,   right );
a QUICKSORT ELEMENTS( left, ub    )
FI # QUICKSORT # ;

# quicksorts a in-place                                                   #
OP   QUICKSORT = ( REF[]INT    a )REF[]INT:    a QUICKSORT ELEMENTS( LWB a, UPB a );
OP   QUICKSORT = ( REF[]REAL   a )REF[]REAL:   a QUICKSORT ELEMENTS( LWB a, UPB a );
OP   QUICKSORT = ( REF[]STRING a )REF[]STRING: a QUICKSORT ELEMENTS( LWB a, UPB a );

# end sort.incl.a68                                                           #```