% MERGESORT
/*
 Predicado: mergesort(L,R)

  Entrada: 
    L: lista de datos 

  Salida
   R: lista ordenada de datos (orden creciente)

  Descripción 
     Split
       Los datos de lista se distribuyen en dos partes de forma alternativa.
       El proceso se repite de forma recursiva 
       hasta que la lista esté compuesta por sublistas con un elemento.
     Merge
       A continuación, se van uniendo de forma ordenada las sublistas de dos en dos. 
         
  Ejemplo 
                [5 4 1 3 2]
Split
            [5 1 2]   |     [4 3]
       [5 2]   | [1]  ||  [4] | [3]
  [5]    | [2] || [1] ||| [4] | [3]

Merge
  [2 5]  | [1] || [ 3 4] 
      [1 2 5]  || [ 3 4] 
          [1 2 3 4 5] 

*/
% Lista vacía
mergesort([],[]):-!.

% Lista con un elemento.
mergesort([A],[A]):-!.

% Lista con dos o más elementos
mergesort([A,B|Cola],S) :-  
   % Se separan los elementos de la lista en dos sublistas
   split([A,B|Cola],L1,L2),
   % Se aplica la recursión a la primera lista
   mergesort(L1,S1),
   % Se aplica la recursión a la segunda lista 
   mergesort(L2,S2),
   % Se unen las listas resultantes
   merge(S1,S2,S).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*

  Predicado auxiliar: split(L,I,D).
  
  Entrada: 
    L: lista de datos 

  Salida
    I: lista con los elementos de L que ocupan un lugar impar
    D: lista con los elementos de L que ocupan un lugar par

  
  Descripción 
    Reparte los elementos de L en dos listas
        En I, los menores que X
        En D, los mayores o iguales que X

  Ejemplos:
    partir([1, 2, 3, 4], I, D).
    I = [1, 3]
    D = [2, 4] 


    partir([a, b, c, d], I, D).
    I = [a, c]
    D = [b, d] 

*/

% Lista vacía
split([],[],[]):-!.

% Lista con un elemento
split([A],[A],[]):-!.

% Lista con dos o más elementos
split([A,B|Cola],[A|ColaI],[B|ColaD]):- split(Cola,ColaI,ColaD).



/*

  Predicado auxiliar: merge(I,D,R).
  
  Entrada: 
    I: lista con datos ordenados
    D: lista con datos ordenados
    
  Salida
  	 R: lista de datos con datos ordenados

  
  Descripción 
    Una los datos de las lista I y D en L

  Ejemplos:
    merge([1, 3], [2, 4],R).
    R= [1, 2, 3, 4]
    
    merge([ a, b, d], [c], R).
    R = [a, b, c, d]
*/


% La segunda lista está vacía
merge(I,[],I):-!.

% La primera lista está vacía
merge([],D,D):-!.

% La cabeza de la primera lista es menor que la cabeza de la segunda lista
merge([A|ColaI],[B|ColaD],[A|Cola]):-  
	% El símbolo @ también permite comparaciones de datos no numéricos  
	A @=< B, 
	!,
	merge(ColaI,[B|ColaD],Cola).

% La cabeza de la segunda lista es menor o igual que la cabeza de la primera lista
merge([A|ColaI],[B|ColaD],[B|Cola]):-  
	% El símbolo @ también permite comparaciones de datos no numéricos 
	A @> B,  
	merge([A|ColaI],ColaD,Cola).