// insertSort

let rec insert x lst =

match lst with

| [] -> [x]

| y::rest -> if x < y then x::y::rest else y::(insert x rest)

let rec insertSort = function

| [] -> []

| x::rest -> insert x (insertSort rest)

// mergeSort

let rec split = function

| [] -> ([], [])

| a::[] -> ([a], [])

| a::b::rest -> let p, q = split rest in (a::p, b::q)

let rec merge p q =

match p, q with

| [], [] -> []

| a, [] -> a

| [], a -> a

| x::xs, y::ys when x<=y -> x::merge xs q

| x::xs, y::ys -> y::merge p ys

let rec mergeSort = function

| [] -> []

| a::[] -> [a]

| lst ->

let p, q = split lst

let ps = mergeSort p

let qs = mergeSort q

merge ps qs

// quickSort

let rec quickSort = function

| [] -> []

| [a] -> [a]

| x::xs ->

quickSort [for y in xs do if y<=x then yield y]

@ [x]

@ quickSort [for y in xs do if y>x then yield y]

## No comments:

## Post a Comment