OCaml mergesort и время

Question

Я создал функцию (mergesort) в ocaml, но когда я ее использую, список инвертируется.

Кроме того, я хочу рассчитать время, которое система принимает для расчета, как я могу это сделать?

let rec merge l x y = match (x,y) with 
    | ([],_) -> y 
    | (_,[]) -> x 
    | (h1::t1, h2::t2) -> 
    if l h1 h2 
     then h1::(merge l t1 y) 
     else h2::(merge l x t2);; 

let rec split x y z = match x with 
    | [] -> (y,z) 
    | x::resto -> split resto z (x::y);; 

let rec mergesort l x = match x with 
    | ([] | _::[]) -> x 
    | _ -> let (pri,seg) = split x [] [] 
    in merge l (mergesort l pri) (mergesort l seg);; 

mergesort (>) [2;6;1;8];; 
- : int list = [8; 6; 2; 1] 

Answer 1

Изменение линии if l h1 h2 по if l h2 h1. Способ сравнения элементов заголовка из двух подсписок дает вам перевернутый список.

Кроме того, я могу предложить вам использовать следующий синтаксис если у вас есть кратные recursives функции, вызывающие друг друга:

let rec merge cmp x y = match (x,y) with 
    | ([],_) -> y 
    | (_,[]) -> x 
    | (h1::t1, h2::t2) -> 
    if cmp h2 h1 
    then h1::(merge cmp t1 y) 
    else h2::(merge cmp x t2) 

and split x y z = match x with 
    | [] -> (y,z) 
    | x::resto -> split resto z (x::y) 

and mergesort cmp x = match x with 
    | ([] | _::[]) -> x 
    | _ -> let (pri,seg) = split x [] [] 
    in (merge cmp (mergesort cmp pri) (mergesort cmp seg));; 

Для измерения функции времени, вы можете посмотреть здесь: Running time in Ocaml

Answer 2

Для сравнения функции см. Core_Bench https://blogs.janestreet.com/core_bench-micro-benchmarking-for-ocaml/.