26 May
2003
26 May
'03
2:59 p.m.
Dear all,
here is the small mergesort program for which ciaopp V0.8#17 (as installed on clip) seems to go away, both in the computation of upper and lower complexity bounds. If you have a version of ciaopp that can analyze it, please let us know the complexity analysis results. Of course, it would be great if we could have a version of ciaopp installed on our machines: too often we wonder "which complexity would be obtained with ciaopp for this program?" We can handle beta or even alpha versions... anything, provided it breathes ;-) Cheers
Roberto
P.S. Same thing applies to ciaoc: as soon as you have a version with the recent memory management fixes, just let us know.
--
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara@cs.unipr.it
:- module(msort, [msort/2], [assertions]).
:- entry msort(A,B) : (list(A, num), var(B), ground(A)).
%
% msort.pl Nai-Wei Lin November, 1991
%
% This program performs the mergesort on a list of integers.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%:- mode(divide/3,[+,-,-]).
%:- measure(divide/3,[length,length,length]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
divide([],[],[]).
divide([X],[X],[]).
divide([X1,X2|L],[X1|L1],[X2|L2]) :-
divide(L,L1,L2).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%:- mode(merge/3,[+,+,-]).
%:- measure(merge/3,[length,length,length]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
merge(L,[],L).
merge([],L,L) :-
L == [].
merge([X1|L1],[X2|L2],[X1|L]) :-
X1 >= X2,
merge(L1,[X2|L2],L).
merge([X1|L1],[X2|L2],[X2|L]) :-
X1 < X2,
merge([X1|L1],L2,L).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%:- mode(msort/2,[+,-]).
%:- measure(msort/2,[length,length]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
msort([],[]).
msort([X],[X]).
msort([X1,X2|L],R) :-
divide([X1,X2|L],L1,L2),
msort(L1,R1),
msort(L2,R2),
merge(R1,R2,R).