Merge sort is a divide an conquer algorithm that relies solely on recursion to sort a list, making it the ideal algorithm to implement in Elixir.

### Understanding the Algorithm

The Algorithm mainly does three things. Lets understand them one by one.

#### Divide

Merge sort divides the input list recursively into halves. It does so until there’s only one element left.

#### Conquer

Single element lists are assumed to be sorted. The Algorithm merges these single element lists by comparing their values to form a sorted list. This is where the ‘merge’ comes in

#### Merge

The merging process compares elements from two sorted lists and combines them into a single sorted list.
It repeatedly takes the smaller `head`

from either list and adds it to the sorted list.
This process is repeated to combine 2 sorted lists to form larger sorted lists.
Thus, the merge process is the brains behind the merge sort algorithm.

Here’s a flow diagram to visualise it clearly -

I’ve attached a helpful video at the end to help you understand it better. Enough chit-chat. Let’s get our hands dirty.

### Implementation

#### The `sort/1`

First up, we need a function to divide the input list recursively into smaller and smaller halves.
The splitting can be achieved by the `Enum.split/2`

function, which returns a tuple containing the split lists.
The split/2 takes an index to split the list, (which in this case is the midpoint of the list), and returns the 2 lists.

```
def sort(list) do
midpoint = div(length(list), 2)
{left, right} = Enum.split(list, midpoint)
merge(sort(left), sort(right))
end
```

We pattern match the 2 halves, and again call the `sort/1`

to recurse on them.

As we split into halves, we ultimately get single-element lists.

Let’s handle them next.

```
def sort([x]), do: [x]
```

Since we want to split into single element lists, we pattern match and just return them, breaking us out of the recursion loop.

Then comes the `merge/2`

function.

#### The `merge/2`

The `merge/2`

must combine 2 sorted lists into a single sorted list.
For this, it needs to compare the `head`

of each of the 2 sorted lists, and merge them accordingly.

In essence, we want to compare the heads & prepend the smaller value, while recursing on the remaining part of the lists.

We have 2 cases to handle.

- When the head of first list is
**less**than head of second list.

We add a gaurd `when l < r`

to handle the first case.
We pattern match with the `[head | tail]`

operator in the function definition itself. This is more elegant than to say `hd(list)`

.

```
def merge([l | left], [r | right]) when l < r do
[l | merge(left, [r | right])]
end
```

- When the head of first list if
**greater**than head of second list.

In this case we have l > r, gaurds are not required. We simply prepend r to the list and recurse on the rest.

```
def merge([l | left], [r | right]) do
[r | merge([l | left], right)]
end
```

Lastly, we add the two exit cases, when we’ve merged the entire list, and only an empty list remains. In that case we want to return the list. We pattern match with an empty list, and return the input list as is.

```
def merge(left, []), do: left
def merge([], right), do: right
```

And there you have it! A complete merge sort algorithm, working in Elixir!

Observe the caveats here. Elixir being a functional programming lanugage, we’ve avoided the use of for-while loops & if-else statements as much as possible. There are a few named functions, each with different arities, that pattern match and call each other multiple times with recursion. This forms the crux of functional programming in Elixir.

Here’s the final code- Give it a try in your `iex`

!

```
defmodule MergeSort do
def sort([]), do: [] # PS: I threw this in just for the sake of completeness. Handles if you pass an empty list
def sort([x]), do: [x]
def sort(list) do
midpoint = div(length(list), 2)
{left, right} = Enum.split(list, midpoint)
merge(sort(left), sort(right))
end
def merge(left, []), do: left
def merge([], right), do: right
def merge([l | left], [r | right]) when l <= r do
[l | merge(left, [r | right])]
end
def merge([l | left], [r | right]) do
[r | merge([l | left], right)]
end
end
```