Translated from https://github.com/ghc/ghc/blob/5d98b8bf249fab9bb0be6c5d4e8ddd4578994abb/libraries/base/Data/OldList.hs#L840

MergeSort.fs

module MergeSort

let sortBy cmp xs =
    let rec sequences xs =
        match xs with
        | a :: b :: xs ->
            if cmp a b > 0
            then descending b [a] xs
            else ascending b (fun ys -> a :: ys) xs
        | xs -> [xs]
    and descending a ``as`` bs =
        match bs with
        | b :: bs when cmp a b > 0 -> descending b (a :: ``as``) bs
        | bs -> (a :: ``as``) :: sequences bs
    and ascending a ``as`` bs =
        match bs with
        | b :: bs when cmp a b <= 0 -> ascending b (fun ys -> ``as`` (a :: ys)) bs
        | bs -> ``as`` [a] :: sequences bs
    let rec merge ``as`` bs =
        match ``as``, bs with
        | a :: as', b :: bs' ->
            if cmp a b > 0
            then b :: merge ``as`` bs'
            else a :: merge as' bs
        | [], bs -> bs
        | ``as``, [] -> ``as``
    let rec mergePairs = function
        | a :: b :: xs -> merge a b :: mergePairs xs
        | xs -> xs
    let rec mergeAll = function
        | [x] -> x
        | xs -> mergeAll (mergePairs xs)
    mergeAll (sequences xs)

let sort xs = sortBy compare xs