% nacteni:
/* ['2.5.2_11.pl']. */

qsort(L,S):- qsort_dl(L,S-[]).

qsort_dl([], A-A).
qsort_dl([H], [H|A]-A) :- !.
%qsort_dl([H|T],S-C) :- divide(H,T,M,V),
%                       qsort_dl(M,M1-A),
%                       qsort_dl(V,V1-B),
%                       append_dl(M1-A,[H|V1]-B,S-C).
%append_dl(A-B,B-C,A-C).

qsort_dl([H|T],M1-B) :- divide(H,T,M,V),
    qsort_dl(M,M1-[H|V1]),
    qsort_dl(V,V1-B).

divide(_,[],[],[]).
divide(H,[K|T],[K|M],V) :- K=<H, !, divide(H,T,M,V).
divide(H,[K|T],M,[K|V]) :- divide(H,T,M,V).

% demonstracni vypis

write_long_list([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10|T]) :-
    write('['), write(X1), write(','), write(X2), write(','), write(X3),
    write(','), write(X4), write(','), write(X5), write(','), write(X6),
    write(','), write(X7), write(','), write(X8), write(','), write(X9),
    write(','), write(X10), write(',...,'), last(T,X), write(X), write(']').

start:- 
    write('Radici algoritmus QuickSort - efektivnejsi varianta'),
    write(' s rozdilovymi seznamy'),nl,nl,
    write('Vysledek volani "qsort([5, 2, 8, 2, 654, 8, 3, 4], L)":'),nl,
    qsort([5, 2, 8, 2, 654, 8, 3, 4], L), write('L = '),write(L),nl,
    write('Vysledek volani "qsort([... 300 000 nahodnych cisel...], L2)":'),nl,
    length(Xs, 300000), maplist(random(0,1000000), Xs),
    qsort(Xs, L2), write('L2 = '),write_long_list(L2),nl.

?-start.
