# Efficient sorting

Peter Schachte pets at cs.mu.OZ.AU
Wed Oct 21 15:49:22 AEST 1998

```Hi Folks,

Here's Richard O'Keefe's SAM sort algorithm, in Prolog.  I haven't
looked at it very closely, but hopefully it won't be hard to translate
it to Mercury.

--
Peter Schachte                | The only thing that makes life possible is
mailto:pets at cs.mu.OZ.AU       | permanent, intolerable uncertainty; not
http://www.cs.mu.oz.au/~pets/ | knowing what comes next.
PGP: finger pets at 128.250.37.3 |     -- ursula K. Le Guin

%   File   : /usr/lib/prolog/samsort
%   Author : Richard A. O'Keefe
%   Updated: 1 June 84
%   Purpose: a sorting routine which exploits existing order

samsort([], []) :- !.
samsort(List, Sorted) :-
samsort(List, [], 0, Sorted).

samsort([], Stack, R, Sorted) :- !,
samfuse(Stack, 0, [Sorted]).
succ(R, S),
samfuse([Run|Stack], S, NewStack),
samsort(Rest, NewStack, S, Sorted).

samfuse([A,B|Rest], K, Ans) :-
0 is K mod 2, !,
J is K div 2,
merge(A, B, C), !,
samfuse([C|Rest], J, Ans).
samfuse(Stack, _, Stack).

sam_run([], Run, [_], Run, []) :- !.
sam_run([Head|Tail], QH, QT, Run, Rest) :-
sam_run(QH, QT, Head, Tail, Run, Rest).

sam_run([Ah|At], Qt, H, T, Run, Rest) :-
H @< Ah, !,
sam_run(T, [H,Ah|At], Qt, Run, Rest).
sam_run(Qh, [Qt], H, T, Qh, [H|T]) :-
H @< Qt, !.
sam_run(Qh, [_,H|Nt], H, T, Run, Rest) :-
sam_run(T, Qh, [H|Nt], Run, Rest).

```