%% --------------------------------------------------------------
%%  Datei:  mergesort.pl
%%  Datum:  28.04.1998
%%  Autor:  Ralf Klinkenberg
%% --------------------------------------------------------------
%%  Programm zum Uebungsblatt 0, Aufgabe 3 (Kuenstliche Intelligenz SoSe 1998).
%%  Programm zum Uebungsblatt 5, Aufgabe 1 (Programmierkurs Prolog SoSe 2002).
%% --------------------------------------------------------------
%%
%%  Aufgabe 5.1:
%%  ------------

% :- [library(basics)].  %% bei Quintus Prolog erforderlich, nicht bei SWI-Prolog

%%  Zusammenfassung zweier sortierter Listen zu einer sortierten Liste
%%  mit 'merge(+SortedList1,+SortedList2,?SortedLongList)':

merge([], Liste, Liste).

merge(Liste, [], Liste).

merge([Kopf1|Rest1], [Kopf2|Rest2], [Kopf1|Liste]) :-
	Kopf1 =< Kopf2,
	merge(Rest1, [Kopf2|Rest2], Liste).

merge([Kopf1|Rest1], [Kopf2|Rest2], [Kopf2|Liste]) :-
	Kopf1 > Kopf2,
	merge([Kopf1|Rest1], Rest2, Liste).

%%  Aufspalten einer Liste in zwei gleichlange (+-1) Listen mit
%%  'split(+LongList,?List1,?List2)':

split([],[],[]).

split([H],[H],[]).

split([K1,K2|Liste],[K1|H1],[K2|H2]) :-
	split(Liste,H1,H2).

%%  MergeSort mit 'mergesort(+UnsortierteListe,?SortierteListe)':

mergesort([],[]).

mergesort([X],[X]).

mergesort(Liste,Sort) :-
	split(Liste,H1,H2),
	mergesort(H1,Sort1),
	mergesort(H2,Sort2),
	merge(Sort1,Sort2,Sort).

%% --------------------------------------------------------------