Insertion Sort implementation with one recursive function and foldBack function

Question

I am reviewing implementations for some basic data structures and the algorithms operating on them. I guess the idiomatic F# code for Insertion Sort is very much like:

let rec insert x = function
  | [] -> [x]
  | y::ys -> if x<=y then x::y::ys
             else y::(insert x ys)

and insertionSort = function
  | [] -> []
  | x::xs -> insert x (insertionSort xs)

let myLst = [8;3;3;5;-6;0;1;4;-3;2]
let result = myLst |> insertionSort 

val result : int list = [-6; -3; 0; 1; 2; 3; 3; 4; 5; 8]

While I was trying to implement it with List.foldBack and only one recursive function, as below, and couldn't give me the correct result? Anyone can figure out where the problem lies?

let rec anotherInsertionSort lst =
  List.foldBack(fun x (ys:list<_>) -> 
                  if ys.IsEmpty then [x]
                  elif x <= ys.Head then x::ys
                  else ys.Head::x::anotherInsertionSort ys.Tail) lst []

Answer 1

Un-golfed from cfern's code:

let rec insert i = function
  | h::t -> min h i::(insert (max h i) t)
  | _ -> [i]

let insertionSort l = List.foldBack insert l []

Answer 2

As I said in my comment, the problem is that you're dropping x in your else branch. Here's one way to fix it:

let rec anotherInsertionSort lst = 
    List.foldBack(fun x ys ->  
                    match ys with
                    | [] -> [x]
                    | y::_ when x <= y -> x::ys 
                    | y::ys -> y::(anotherInsertionSort (x::ys))) lst [] 

Having said that, I like Daniel's approach better.