%
% qsort.prolog
%
% Developed by Ondrej Jombik <nepto@platon.sk>
% Copyright (c) 2005 Platon SDG, http://platon.sk/
% Licensed under terms of GNU General Public License.
% All rights reserved.
%
% Changelog:
% 2005-05-02 - created
%

% $Platon$

qsort([], []).
qsort([X|Xs], Sorted) :-
	partition(Xs, X, Small, Large),
	qsort(Small, Small1),
	qsort(Large, Large1),
	append(Small1, [X|Large1], Sorted).

partition([], _, [], []).
partition([X|Xs], P, [X|Small], Large) :-
	X < P, partition(Xs, P, Small, Large).
partition([X|Xs], P, Small, [X|Large]) :-
	X >= P,partition(Xs, P, Small, Large).