понимание merge sort in ML

Question

У меня есть задание перевести следующий код ML на Java, но я не могу сказать, что он делает. Что здесь делают функции «halfve» и «merge»?

fun halve nil = (nil, nil) 
| halve [a] = ([a], nil) 
| halve (a :: b :: cs) = 
     let 
     val (x, y) = halve cs 
     in 
     (a :: x, b :: y) 
     end; 

fun merge (nil, ys) = ys 
| merge (xs, nil) = xs 
| merge (x :: xs, y :: ys) = 
     if (x > y) then x :: merge(xs, y :: ys) 
     else y :: merge(x :: xs, ys); 

fun mergeSort nil = nil 
| mergeSort [a] = [a] 
| mergeSort theList = 
     let 
     val (x, y) = halve theList 
     in 
     print("xList: "^printList(x)); 
     print("yList: "^printList(y)); 
     merge(mergeSort x, mergeSort y) 
     end; 

Answer 1

halve разбивает список на две части, добавив его элементы чередованием к двум спискам (это избавляет от необходимости вычислять длину первого и затем расщепление его, что потребует 1,5 обходов из списка, а не просто один).

merge объединяет два списка в порядке убывания.

mergeSort разделяет список пополам, сортирует две половины, затем объединяет отсортированные подсписки.