# Going Functional : Merge and Quicksort in F#

Continuing our functional journey, in this post I will first present the Java based implementation of merge sort followed by F# based implementation. Finally we will repeat the same steps for QuickSort algorithm. Java based implementation of the sorting algorithms is taken from Algorithms 4th Edition by **Robert Sedgewick** and **Kevin Wayne**.

### Merge Sort

Following is the Java based implementation of **MergeSort**, which uses an auxiliary array for maintaining intermediate values.

// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

// copy to aux[]

for (int k = lo; k <= hi; k++) {

aux[k] = a[k];

}

// merge back to a[]

int i = lo, j = mid+1;

for (int k = lo; k <= hi; k++) {

if (i > mid) a[k] = aux[j++];

else if (j > hi) a[k] = aux[i++];

else if (less(aux[j], aux[i])) a[k] = aux[j++];

else a[k] = aux[i++];

}

}

// mergesort a[lo..hi] using auxiliary array aux[lo..hi]

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

if (hi <= lo) return;

int mid = lo + (hi - lo) / 2;

sort(a, aux, lo, mid);

sort(a, aux, mid + 1, hi);

merge(a, aux, lo, mid, hi);

}

Next is the F# implementation. The F# implementation replicates exactly the same pattern and codebase as we see in the above code.

let privateMerge(data: int array) (aux : int array) low mid high =

let mutable i = low

let mutable j = mid + 1

for k in low..high do aux.[k] <- data.[k]

for k in [low..high] do

data.[k] <- match k with

| _ when (i > mid) -> j <- j + 1; aux.[j - 1]

| _ when j > high -> i <- i + 1; aux.[i - 1]

| _ when aux.[j] < aux.[i] -> j <- j + 1; aux.[j - 1];

| _ -> i <- i + 1; aux.[i - 1];

let rec privateSort(data: int array) (aux : int array) low high =

match low, high with

| _,_ when high <= low -> ()

| _ ->

let mid = low + (high - low) / 2

Sort data aux low mid

Sort data aux (mid+1) high

Merge data aux low mid high

()

let MergeSort (data: int array) (aux : int array) low high =

Sort data aux low high

printfn "%A" data

Notice how pattern matching has been used instead of iterative for and while loop. General advise when programming in F# is to try and avoid for and while loop and instead try and focus on pattern matching along with recursive functions.One more thing to note in the “**Merge**” method is how the return value of the pattern matching expression is assigned to the “**data**” array index element. This highlights the power of F# wherein if-else block, pattern matching block are expressions which return values.

### Quick Sort

Next lets move on to the implementation of **Quicksort** algorithm. First the Java based implementation.

// quicksort the subarray from a[lo] to a[hi]

private static void sort(Comparable[] a, int lo, int hi) {

if (hi <= lo) return;

int j = partition(a, lo, hi);

sort(a, lo, j-1);

sort(a, j+1, hi);

}

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]

// and return the index j.

private static int partition(Comparable[] a, int lo, int hi) {

int i = lo;

int j = hi + 1;

Comparable v = a[lo];

while (true) {

// find item on lo to swap

while (less(a[++i], v))

if (i == hi) break;

// find item on hi to swap

while (less(v, a[--j]))

if (j == lo) break; // redundant since a[lo] acts as sentinel

// check if pointers cross

if (i >= j) break;

exch(a, i, j);

}

// put partitioning item v at a[j]

exch(a, lo, j);

// now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]

return j;

}

Unlike F#’s Mergesort algorithm, the Quicksort algorithm implementation turned out to be a bit more complicated.

let privatePartition(data: int array) low high =

let mutable i = low

let mutable j = high + 1

let pivot = data.[low]

letlessx y = x <= y

letexchangex y =

let temp = data.[x];

data.[x] <- data.[y];

data.[y] <- temp;

y

let recproc_is =

match s+1 with

| x when less data.[x] pivot && x <> high -> proc_i x;

| _ -> s+1

let recproc_jt =

match t-1 with

| x when less pivot data.[x] && x <> low -> proc_j x;

| _ -> t-1

let recpartition_datas t =

match (proc_i s), (proc_j t) with

| x , y when x >= y -> y

| x , y -> exchange x y |> partition_data x

j <- partition_data i j

exchange low j

let rec private Sort (data: int array) low high =

match low, high with

| _ , _ when high <= low -> ()

| _ ->

let j = Partition data low high

Sort data low (j - 1)

Sort data (j + 1) high

()

let QuickSort (data: int array) low high =

Sort data low high

printfn "%A" data

The structure of the above code is very much similar to what we have in Java based implementation. Its just that I have strictly tried to avoid **while** & **for** loop. In the partition method, the proc_I & proc_j recursive methods identify the I & j index values wherein the values have to be swapped. Note how inside the **Partition **method, I have declared helper functions like **less, exchange, proc_i , proc_j and partition_data**. If you found the above implementation complicated, then I will agree with you. I am still trying to learn F# language and I am very much sure that anyone who holds a better command on the language can write the above code in much simpler manner. If you are one of them, then I request you to please leave your comments.

Thanks.