/*======================================================================
  File			:  mar_quicksort.pl
  Author(s)		:  Mauricio Ayala Rincon
  Modified by		:  
  Last modification	:  Oct. 26 1998
========================================================================*/

/************************************************************************/
% This program sorts lists by the quicksot method 
/************************************************************************/

append([X|Xs], Y, [X|Z]) :- append(Xs,Y,Z).
append([], Y,Y).

quicksort([X | Rl], Lr) :- partition(Rl,X,Menores,Maiores),
                           quicksort(Menores,Lm),
                           quicksort(Maiores,LM),
                           append(Lm,[X | LM], Lr).
quicksort([],[]).

partition([X | Rl], Y,[X | L1], L2) :- X =< Y,
                                       partition(Rl,Y,L1,L2).

partition([X | Rl], Y, L1,[X | L2]) :- X > Y, 
                                       partition(Rl,Y,L1,L2).

partition([],Y,[],[]).