PowerPoint Presentation

Bottom-Up Mergesort in rex (1)

// first the initial list is transformed to a list of 1-element

// lists, then those lists are merged repeatedly

merge_sort(List) = merge_repeatedly( map((X) => [X], List ) );

// merge_repeatedly merges pairs in a list of lists until there

// is only one list left.

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

merge_repeatedly(Lists) => // more than one list left

merge_repeatedly( merge_pairs(Lists) );