# F# Insertion sort

Posted on

Problem

I made a simple insertion sort in F#, it uses a tail recursive `shift` function that attempts to shift an element in a list until it is in the right order. Would like some feedback on the design.

``````let insertionSort xs =
let shiftInsert xs x =
let rec shift xs x f =
match xs with
| [] ->
f() @ [x]
| hd::tl ->
if x < hd then
f() @ x::hd::tl
else
shift tl x (fun () -> f() @ [hd])
shift xs x (fun () -> [])
List.fold shiftInsert [] xs
``````

Solution

1. Why do you always create a function `f` :

`shift tl x (fun () -> f() @ [hd])`

`f() @ x::hd::tl`

2. In your inner function `shift` the parameter `x` is not used – you don’t need to pass it each time you call.

So, you can rewrite as:

``````let insertionSort xs =
let shiftInsert xs x =
let rec shift xs f =
match xs with
| [] ->
f @ [x]
| hd::tl ->
if x < hd then
f @ x::hd::tl
else
shift tl (f @ [hd])
shift xs []
List.fold shiftInsert [] xs
``````

As @JohnPalmer written in the comments instead of `@` better to change the algorithm with using operator “::”

``````let insertionSort xs =
let shiftInsert xs x =
let rec shift xs acc isAdd =
| [], true -> acc
| [], false -> x::acc
| h::t, false ->
if h <= x then
shift t (h::acc) false
else
shift t (h::x::acc) true
|h::t,true ->
shift t (h::acc) true
shift xs [] false
|> List.rev
List.fold shiftInsert [] xs
``````

I’m not sure if the objective was insertion sort or tail recusion? In any case the performance is rather bad for larger data sets.

If insertion sort was the focus the following approach is maybe somewhat more straightforward:

``````let insertionSort xs =
let fold res x =
let index = res |> List.tryFindIndex (fun n -> n > x)
match index with
| None -> res @ [x]
| Some i ->
let start, tail = res |> List.splitAt i
start @ x :: tail

xs |> List.fold fold []
``````