/* sort.q: collection of sorting algorithms
   $Id: sort.q,v 1.2 2004/01/28 16:54:43 agraef Exp $ */

/* This file is part of the Q programming system.

   The Q programming system is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   The Q programming system 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 General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

/* Algorithms to sort lists stably using a given order predicate. */

include stdlib;

public msort P Xs, qsort P Xs;

/* msort: merge sort algorithm */

private gr, lq, runs, add_run, sort_runs, merge_runs, merge;

gr P X Y		= P Y X;
lq P X Y		= not gr P X Y;

msort P Xs:List		= sort_runs P (runs P Xs);

runs P			= foldr (add_run P) [];
add_run P X []		= [[X]];
add_run P X [[Y|Ys]|Yss]= [[X,Y|Ys]|Yss] if lq P X Y;
			= [[X],[Y|Ys]|Yss] otherwise;

sort_runs P []		= [];
sort_runs P [Xs]	= Xs;
sort_runs P Xss		= sort_runs P (merge_runs P Xss) otherwise;

merge_runs P []		= [];
merge_runs P [Xs]	= [Xs];
merge_runs P [Xs,Ys|Xss]= [merge P Xs Ys|merge_runs P Xss];

merge P [] Ys		= Ys;
merge P Xs []		= Xs;
merge P [X|Xs] [Y|Ys]	= [X|merge P Xs [Y|Ys]] if lq P X Y;
			= [Y|merge P [X|Xs] Ys] otherwise;

/* qsort: quicksort algorithm */

qsort P []              = [];
qsort P [X|Xs]          = qsort P (filter (gr P X) Xs) ++
			  [X|qsort P (filter (lq P X) Xs)];