Merge Sort

Table of Contents

Elixir DSA - This article is part of a series.

Part 3: This Article

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 -

graph TD A[Start] --> B{Is list length > 1?} B -->|Yes| C[Divide list into two halves] B -->|No| D[Return list] C --> E[Recursively sort left half] C --> F[Recursively sort right half] E --> G[Merge sorted halves] F --> G G --> H[Return merged list] D --> I[End] H --> I

Here’s a demo of that with a sample list-

graph TD Start([Start]) --> Init[["Initial Array: [8, 3, 2, 5, 1, 7, 6, 4]"]] Init --> Divide1["Divide: [8, 3, 2, 5] [1, 7, 6, 4]"] Divide1 --> Divide2["Divide: [8, 3] [2, 5] [1, 7] [6, 4]"] Divide2 --> Divide3["Divide: [8] [3] [2] [5] [1] [7] [6] [4]"] Divide3 --> Merge1["Merge: [3, 8] [2, 5] [1, 7] [4, 6]"] Merge1 --> Merge2["Merge: [2, 3, 5, 8] [1, 4, 6, 7]"] Merge2 --> FinalMerge["Final Merge: [1, 2, 3, 4, 5, 6, 7, 8]"] FinalMerge --> End([End])

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