Coding in F#

In this problem and the next, I ask you to analyze code, as discussed in the last section of the Checklist. Suppose we wish to define an F# function to sort a list of integers into non-decreasing order. For example, we would want the following behavior:

> sort [3;1;4;1;5;9;2;6;5];;

val it : int list = [1; 1; 2; 3; 4; 5; 5; 6; 9]

We might try the following definition:

let rec sort = function

| [] -> []

| [x] -> [x]

| x1::x2::xs -> if x1 <= x2 then x1 :: sort (x2::xs)

else x2 :: sort (x1::xs)

Analyze the correctness of this definition with respect to the Checklist for Programming with Recursion.