Bottom-Up Mergesort in rex (2)
// merge_pairs merges pairs of lists in a list until none is left.

merge_pairs([]) => [];                          // no more lists

merge_pairs([A]) => [A];                        // only one list

merge_pairs([A, B | L]) => [merge(A, B) | merge_pairs(L)];


// merge creates a single ordered list from two ordered lists

merge(L, []) => L;

merge([], M) => M;

merge([A | L], [B | M]) =>
  A <= B ? [A | merge(L, [B | M])] : [B | merge([A | L], M)];