Сортировка слиянием для фа-диеза

В обеих ваших функциях у вас была проблема, заключающаяся в том, что последний шаг, который вы делаете, - это не рекурсивный вызов, а что-то другое:

• в merge это :: операция
• в mergesort это merge

Итак, вам нужно добраться до точки, где самым последним будет рекурсивный вызов!

Одна из возможностей в ситуациях, когда вам нужно сделать более одного рекурсивного вызова, - это использовать продолжения - идея состоит в том, чтобы передать функцию, которая должна вызываться с результатом текущего шага, а затем продолжить вычисление. оттуда.

это хвостовая рекурсивная версия mergesort, использующая эту технику:

let mergesort xs = 
    let rec msort xs cont = 
        match xs with
        | []    -> cont []
        | [x]   -> cont xs
        | _     -> 
            let mid = List.length xs / 2
            let (xs', xs'') = List.splitAt mid xs
            msort xs' (fun ys' -> msort xs'' (fun ys'' -> cont (merge ys' ys'')))
    msort xs id

как вы можете видеть, идея не такая уж и сложная - вместо первого вызова обоих рекурсивных путей он начинается только с одной половины, но добавляет продолжение, которое в основном говорит:

как только у меня будет результат mergesort xs', я беру результат ys' и продолжаю mergesorting xs'', а затем объединяю эти

конечно, второй шаг выполняется точно так же (вставьте merge в продолжение)

самое первое продолжение обычно является идентификатором, как вы можете видеть в самой последней строке;)

и вот что-то подобное для вашего merge:

let merge xs ys = 
    let rec mrg xs ys cont =
        match (xs, ys) with
        | ([], ys) -> cont ys
        | (xs, []) -> cont xs
        | (x::xs', y::ys') ->
            if x < y 
            then mrg xs' ys (fun rs -> cont (x::rs))
            else mrg xs ys' (fun rs -> cont (y::rs))
    mrg xs ys id

они, конечно, займут столько же места в куче (возможно, больше) - но обычно это не проблема - ваш стек должен быть в порядке;)

Каждый рекурсивный вызов требует места в стеке. Чем больше раз вызывает себя mergesort, тем больше используется стек.

Вы избегаете переполнения стека с помощью рекурсивной функции, используя хвостовую рекурсию. Это просто означает, что последнее, что делает функция, - это вызывает саму себя, вызов удаляется и вместо этого превращается в прыжок, экономя место в стеке.

В вашем случае это сложно сделать, потому что вам придется дважды вызывать слияние. Только один из них может быть последним. Решение - использовать продолжение. . Вы вызываете слияние только один раз, но передаете ему функцию для вызова, которая вызовет слияние во второй раз.

Поищите в Интернете примеры F # сортировки слиянием, в которой используются продолжения.