/* File:      qsort.P
** Author(s): Jiyang Xu, Kostis Sagonas
** Contact:   xsb-contact@cs.sunysb.edu
** 
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
** Copyright (C) ECRC, 1990
** 
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
** 
** XSB is distributed in the hope that it will be useful, but WITHOUT ANY
** WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
** FOR A PARTICULAR PURPOSE.  See the GNU Library General Public License for
** more details.
** 
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: qsort.P,v 1.1.1.1 1998/11/05 17:01:01 sbprolog Exp $
** 
*/

:- export demo/0, qsort/2.

/* time for compiling this module (naive qsort without if-then-else):

	Sepia 2.12a:		2.03 sec (2.33 before loading lists.pl)
	SBProlog double -O:	3.10 sec (5.22 before loading )
	XSB (optimized):	0.53 seconds

*/

demo :- qsort([3,5,6,2,7,1], R), write(R).

qsort([X|T],R) :-
	part(X,T,U1,U2),
	qsort(U1,V1),
	qsort(U2,V2),
	append(V1,[X|V2],R).
qsort([],[]).

part(M,[E1|T],[E1|U1],U2) :-
	E1 =< M, part(M,T,U1,U2).
part(M,[E1|T],U1,[E1|U2]) :-
	E1 > M, part(M,T,U1,U2).
part(_,[],[],[]).

append([],X,X).
append([H|L1],L2,[H|L3]) :- append(L1,L2,L3).