% Author:
% Date: 03/11/2010
% quicksort

%quicksort(L,Ltriee).

quicksort([],[]).

quicksort([X|L],Ltriee) :-
                        partition(L,X,Petits,Grands),
                        quicksort(Petits,PetitsTries),
                        quicksort(Grands,GrandsTries),
                        append(PetitsTries,[X|GrandsTries],Ltriee).
                        
partition([],_Y,[],[]).

partition([X|L1],Y,[X|L3],L4) :-
                              X < Y,
                              partition(L1,Y,L3,L4).
                              
partition([X|L1],Y,L3,[Y|L4]) :-
                              X >= Y,
                              partition(L1,Y,L3,L4).

% http://fr.wikipedia.org/wiki/Tri_par_insertion
insertionSort([],[]).

insertionSort(Unsorted,[Minima|Sorted_Rest]) :-
                           min_list(Unsorted,Minima),
                           delete(Unsorted,Minima,New_Unsorted),
                           insertionSort(New_Unsorted,Sorted_Rest).
                           
% http://www710.univ-lyon1.fr/~nguin/Prolog/Cours/Cours3-Tris-arbres.pdf
% http://fr.wikipedia.org/wiki/Tri_par_selection
selectionSort([First_Unsort|Unsorted],Sorted) :-
                                     selectionSort(Unsorted,Newly_Sorted),
                                     insert(Newly_Sorted,First_Unsort,Sorted).

selectionSort([],[]).

insert([],X,[X]).
                
insert([H|Q],X,[H|L]) :-
                X > H,
                insert(Q,X,L).

insert([H|Q],X,[X,H|Q]) :-
                X =< H.

mergeSort([],[]).

mergeSort(Unsorted,Sorted) :-
                           split(Unsorted,UnsortedPart),
                           merge(UnsortedPart,Sorted).
                           
split([],[]).

split([X|R],[[X]|L]) :-
               split(R,L).
               
merge(Unsorted,Sorted) :-
                        length(Unsorted, Size),
                        Size > 1,
                        refine(Unsorted,Newly_Unsorted),
                        merge(Newly_Unsorted,Sorted).


merge([Unsorted],Unsorted) :-
                        length([Unsorted], Size),
                        Size = 1.

refine([],[]).

refine([X,Y|Unsorted],[SubResult1|SubResult2]) :-
                                 mergeSubList(X,Y,SubResult1),
                                 refine(Unsorted,SubResult2).

refine([X],[X]).

mergeSubList([],L,L) :- !.
mergeSubList(L,[],L) :- !.

mergeSubList([X1|R1],[X2|R2],[X2|L]) :-
                                     X1 > X2,
                                     mergeSubList([X1|R1],R2,L).
                                   
mergeSubList([X1|R1],[X2|R2],[X1|L]) :-
                                     X1 =< X2,
                                     mergeSubList(R1,[X2|R2],L).