%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Lazy mergesort in Oz

% Author: Peter Van Roy (upon suggestion by Miller Puckette)
% Date: Aug. 27, 2008

% This sort routine has the same good incremental property as
% lazy quicksort, and in addition is guaranteed logarithmic.
% Getting the first element: Split the list and get the first
% element of the Merge.  This gets the first elements of the
% two halves of the split, and so forth recursively.  O(n) work
% to get the first element.

% Suggested by Miller Puckette at ICMC 2008 after I explained
% to him how the lazy quicksort works.

declare
proc {Split Xs Ys Zs}
   case Xs
   of nil then Ys=nil Zs=nil
   [] [X] then Ys=[X] Zs=nil
   [] X1|X2|Xr then Yr Zr in
      Ys=X1|Yr
      Zs=X2|Zr
      {Split Xr Yr Zr}
   end
end

fun lazy {Merge Xs Ys}
   case Xs#Ys
   of nil#Ys then Ys
   [] Xs#nil then Xs
   [] (X|Xr) # (Y|Yr) then
      if X<Y then X|{Merge Xr Ys}
      else Y|{Merge Xs Yr} end
   end
end

fun lazy {MergeSort Xs}
   case Xs
   of nil then nil
   [] [X] then [X]
   else Ys Zs in
      {Split Xs Ys Zs}
      {Merge {MergeSort Ys} {MergeSort Zs}}
   end
end

declare
Ys={MergeSort [1 9 2 8 3 7 4 6 5]}
{Browse Ys}

{Browse Ys.2.2.2.1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%