write program using SML language

Higher order ML Functions

1. Write a function merge_sort: (a * a -> bool) -> a list -> a list that takes a comparison function and then a list, and return a sorted list in the order specified by the comparison function.

For example, merge_sort (op >) [0, 5, 1, ~4, 9, 11]

evaluates to [11,9,5,1,0,~4].

2. Write a function selection_sort: (a * a -> bool) -> a list -> a list that takes a comparison function and then a list, and return a sorted list in the order specified by the comparison function.

Selection sort orders a list from the left to right by selecting the least element from the unsorted portion of the list and adds it to the partially sorted list. Note that the least element is not necessarily the smallest or largest element it depends on the comparison function passed to selection_sort.

For example, selection_sort (op >) [0, 5, 1, ~4, 9, 11]

evaluates to [11,9,5,1,0,~4].

The computation has the following steps:

[0, 5, 1, ~4, 9, 11] select 11

-> 11::[0, 5, 1, ~4, 9] select 9

-> 11::9::[0, 5, 1, ~4] select 5

-> 11::9::5::[0, 1, ~4] select 1

-> 11::9::5::1::[0, ~4] select 0

-> 11::9::5::1::0::[~4] select ~4

-> 11::9::5::1::0::~4::nil

You should implement a helper function select: a list -> a list as an inner function to selection_sort. The select function takes a 1 list and returns the list with the least element in front.

For example, select [0,5,1,~4,9,11] should return [11,0,5,1,~4,9] given the ordering function op >.

3. Write a function insertion_sort: (a * a -> bool) -> a list -> a list that takes a comparison function and then a list, and return a sorted list in the order specified by the comparison function.

Insertion sort orders a list from left to right by inserting an element from unsorted portion of the list into the correct position in the sorted portion of the list.

For example, insertion_sort (op >) [0, 5, 1, ~4, 9, 11]

evaluates to [11,9,5,1,0,~4].

The computation has the following steps:

nil [0, 5, 1, ~4, 9, 11] insert 0

-> [0] [5, 1, ~4, 9, 11] insert 5

-> [5, 0] [1, ~4, 9, 11] insert 1

-> [5, 1, 0] [~4, 9, 11] insert ~4

-> [5, 1, 0, ~4] [9, 11] insert 9

-> [9, 5, 1, 0, ~4] [11] insert 11

-> [11, 9, 5, 1, 0, ~4] nil

You should implement two helper functions as inner functions.

The first function insert:a list * a -> a list takes a sorted list l and an element x and insert x into the right position of l so that the list remains sorted after insertion.

For example, insert ([5,1,0,~4], 9) should evaluates to [9,5,1,0,~4].

Again the order depends on the comparision function passed to insertion_sort.

The second helper function sort:a list * a list -> a list takes a sorted list sofar and an unsorted list l and inserts the elements of l into sofar.