F# sort using head::tail

I am trying to write a recursive function that uses head::tail. I understand that head in the first element of the list and tail is all other elements in the list. I also understand how recursions works. What I am wondering is how to go about sorting the elements in the list. Is there a way to compare the he开发者_如何学JAVAad to every element in the tail then choose the smallest element? My background in C++ and I am not allowed to use the List.sort(). Any idea of how to go about it? I have looked at the tutorials on the msdn site and still have had no luck

---

Here is recursive list-based implementation of quicksort algorithm in F#

let rec quicksort list =
    match list with
    | [] -> []
    | h::t ->
        let lesser = List.filter ((>) h) t
        let greater = List.filter ((<=) h) t
        (quicksort lesser) @[h] @(quicksort greater)

---

You need to decide a sorting methodology before worrying about the data structure used. If you were to do, say, insertion sort, you would likely want to start from the end of the list and insert an item at each recursion level, being careful how you handle the insertion itself.

Technically at any particular level you only have access to one data element, however you can pass a particular data element as a parameter to preserve it. For instance here is the inserting part of an insertion sort algorithm, it assumes the list is sorted.

let rec insert i l =
    match l with
    | [] -> [i]
    | h::t -> if h > i then
                  i::l
              else
                  h::(insert i t)

Note how I now have access to two elements, the cached one and the remainder. Another variation would be a merge sort where you had two sorted lists and therefore two items to work with any particular iteration.

Daniel's commented answer mentions a particular implementation (quicksort) if you are interested.

Finally list's aren't optimal for sorting algorithms due to their rigid structure, and the number of allocations required. Given that all known sorting algorithms are > O(n) complexity, you can translate you list to and from an array in order to improve performance without hurting your asymptotic performance.

EDIT:
Note that above isn't in tail recursive format, you would need to do something like this:

let insert i l =
    let rec insert i l acc =
        match l with
        | [] -> List.foldBack (fun e a -> e :: a) acc [i]
        | h::t -> if h > i then
                      List.foldBack (fun e a -> e :: a) acc i::l
                  else
                      insert i l (i::acc)
    insert i l []

I don't remember offhand the best way to reverse a list so went with an example from https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/lists