```    1:- module(miser_sort, []).    2:- use_module(miser).    3
4:- miserly(miser_sort/2, [tiny_sort,permutation_sort,merge_sort,quick_sort]).    5
6verify :-
7    Sorters = [tiny_sort,permutation_sort,merge_sort,quick_sort],
8    forall(member(Sorter, Sorters), verify(Sorter)).
9
10verify(Sorter) :-
11    format('Verifying ~p ... ', [Sorter]),
12    flush_output,
13    forall(between(1,100, _), verify_work(Sorter)),
14    format('done~n').
15
16verify_work(Sorter) :-
17    (Sorter=tiny_sort -> MaxLen=3
18    ;Sorter=permutation_sort -> MaxLen=10
19    ;MaxLen=30
20    ),
21    random_list(MaxLen, Xs),
22    (   call(Sorter, Xs, Sorted)
23    ->  ( is_sorted(Sorted)
24        -> true
25        ;   format('BAD! ~w => ~w~n', [Xs, Sorted])
26        )
27    ;   format('QUIT ~w~n', [Xs])
28    ).
29
30random_list(MaxLen, Xs) :-
31    Len is random(MaxLen),
32    length(Xs, Len),
33    lucky(Xs).
34
35
36lucky([]).
37lucky([X|Xs]) :-
38    X is random(100),
39    lucky(Xs).
40
41% true if elements of Xs are sorted in increasing order
42is_sorted([]).
43is_sorted([_]) :- !.
44is_sorted([X,Y|Rest]) :-
45    X @=< Y,
46    is_sorted([Y|Rest]).
47
48
49% test every permutation of Xs looking for one that's sorted
50permutation_sort(Xs, Sorted) :-
51    length(Xs, Len),
52    Len < 10,   % takes too long on longer lists
53    permutation(Xs, Sorted),
54    is_sorted(Sorted),
55    !.  % only want the first sorted permutation
56
57
58% hardcoded sort for tiny lists
59tiny_sort([],[]).
60tiny_sort([X], [X]) :- !.
61tiny_sort([A,B], [X,Y]) :-
62    (   A @=< B
63    ->  X=A, Y=B
64    ;   X=B, Y=A
65    ).
66tiny_sort([A,B,C], Sorted) :-
67    (A @=< B -> AB=ab ; AB=ba),
68    (A @=< C -> AC=ac ; AC=ca),
69    (B @=< C -> BC=bc ; BC=cb),
70    tiny_sort_table(AB, AC, BC, A, B, C, Sorted).
71
72tiny_sort_table(ab, ac, bc, A, B, C, [A,B,C]) :- !.
73tiny_sort_table(ab, ac, cb, A, B, C, [A,C,B]) :- !.
74tiny_sort_table(ab, ca,  _, A, B, C, [C,A,B]) :- !.
75tiny_sort_table(ba, ac,  _, A, B, C, [B,A,C]) :- !.
76tiny_sort_table(ba, ca, bc, A, B, C, [B,C,A]) :- !.
77tiny_sort_table(ba, ca, cb, A, B, C, [C,B,A]) :- !.
78
79
81merge_sort([], []) :- !.
82merge_sort([X], [X]) :- !.
83merge_sort(Xs, Ys) :-
84    divide(Xs, Left0, Right0),
85    merge_sort(Left0, Left),
86    merge_sort(Right0, Right),
87    merge(Left, Right, Ys).
88
89divide(Xs, Left, Right) :-
90    length(Xs, Len),
91    Target is round(Len/2),
92    divide_loop(Target, Xs, [], Left, Right).
93
94divide_loop(0, Right, Accum, Left, Right) :-
95    reverse(Accum, Left),
96    !.
97divide_loop(N, [X|Xs], Accum, Left, Right) :-
98    N1 is N-1,
99    divide_loop(N1, Xs, [X|Accum], Left, Right).
100
101merge([], Ys, Ys) :- !.
102merge(Xs, [], Xs) :- !.
103merge([X|Xs], [Y|Ys], [Smaller|Rest]) :-
104    (   X @=< Y
105    ->  Smaller = X,
106        merge(Xs, [Y|Ys], Rest)
107    ;   Smaller = Y,
108        merge([X|Xs], Ys, Rest)
109    ).
110
111
112% standard quick sort
113quick_sort([],[]).
114quick_sort([X], [X]) :- !.
115quick_sort([Pivot|Xs], Sorted) :-
116    partition('@>'(Pivot), Xs, Left, Right),
117    quick_sort(Left, LeftSorted),
118    quick_sort(Right, RightSorted),
119    append(LeftSorted, [Pivot|RightSorted], Sorted)```