/* 

  Merge sort (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.


go =>
  N = 1000,
  L = [random2() mod N:  _ in 1..N],
  msort(L,S),
  println(S),
  L.sort() == S,
  println(true),
  nl.

go2 =>
  L  = ["UK London", "US New York", "US Boston", "US Washington",
        "UK Washington", "US Birmingham", "UK Birmingham", "UK Boston"],
  msort(L,S),
  println(S),
  L.sort() == S,
  println(true),
  nl.


% Prolog version
% msort( L, S )
% True if S is a sorted copy of L, using merge sort
msort( [], S ) ?=>  S = [].
msort( [X], S ) ?=> S = [X].
msort( U, S ) => split(U, L, R), msort(L, SL), msort(R, SR), merge(SL, SR, S).
 
% split( LIST, L, R )
% Alternate elements of LIST in L and R
split( [], L, R )  ?=> L = [], R = [].
split( [X], L, R ) ?=> L = [X], R = [].
split( [L,R|T], LLT, RRT ) => 
  LLT = [L|LT],
  RRT = [R|RT],
  split( T, LT, RT ).
 
% merge( LS, RS, M )
% Assuming LS and RS are sorted, True if M is the sorted merge of the two
merge( [], RS, M ) ?=> M = RS.
merge( LS, [], M ) ?=> M = LS.
merge( [L|LS], RRS, LT ) ?=>
    RRS = [R|RS],
    LT = [L|T],
    L @=< R, 
    merge(LS, [R|RS], T).
merge( [L|LS], RRS, RT ) =>
    RRS = [R|RS],
    RT = [R|T],
    L @> R, merge( [L|LS],   RS,  T).