# Merge Sorting Algorithm in Go

There are so many ways and ** well known algorithms** for

**. Some of them are more or less efficient than others. Some perform**

*sorting data**faster*, others use

*less memory*and when it comes to a job like sorting, there is

**which works the best for all the cases.**

*no best all in one solution*That’s why in this article we’ll focus our attention on ** Merge Sorting Algorithm**, by covering everything from

*how it works*under the hood till

*implementing*it step by step in

*Go*aka

*Golang*.

Before we dive into the topic, I wanted to let you know that I’m more active on YouTube @ ** SteveHook** where I create

*videos*on many more other topics. Also feel free to check out the

**where I stored all the**

*repo**resources*,

*presentation notes, animations*&

*coding examples.*

# Overview

Before we throw in code and how the algorithm works technically, what I usually love to begin things with are *day by day examples*, meaning we’re going to go back to our good old ** deck of cards**.

The easiest way to reason about the algorithm is: imagine you want to sort a big ** pile of cards**. What you’d typically do, is keep on

**the pile in**

*dividing*

*2***and**

*smaller piles***the process, till each bigger pile is divided in very small piles consisting of**

*repeat***, after which you start**

*1 card***all the piles back into 1 pile. When merging 2 piles into 1 is important to keep the**

*merging***order in mind.**

*sorting*By repeating this ** recursive process,** which is also known as the

**principle. We**

*Divide & Conquer***into**

*split the big problem***, then**

*smaller problems***each**

*solve***and at the end we**

*individual problem***the**

*merge***, thus solving the big initial problem.**

*solutions*# The Algorithm Overview

Now that we know what is the *Merge Sort* algorithm in a nutshell, let us define couple of rules and technical *steps* required for this algorithm to work.

- On every call find the
of the incoming array/slice (*middle*)*divide it in 2* the*Sort*side (recursively)*LEFT*the*Sort*side (recursively)*RIGHT*the*Merge*&*LEFT*side (recursively)*RIGHT*- Array/Slice of
is considered*1 element**sorted* the process using the*Repeat*principle (Recursive)*Divide & Conquer*

Here’s a small example of how the process pretty much looks:

# The Divide & Conquer Principle

While every problem out there can be solved using the good old procedural approach, in many cases using a *Divide & Conquer* or recursive approach is just much easier and simpler in order to solve a problem.

The Divide & Conquer principle consists of 3 simple steps:

the problem into*Divide*problems of the*smaller**same type*the process till the problem can*Repeat**no longer be divided*- Collect &
indivisible problems (solutions) or*Merge**Conquer*

That’s the *Divide & Conquer* principle in a nutshell or we just call it a recursive approach. This is how the recursive approach looks like for our specific *Merge Sorting Algorithm*:

- We’ll start by dividing the
into*slice**smaller slices* - When each slice consists of
only we*1 element*the*start*process*merging* - In the
process we also*merging*the resulting slice*sort out*

This way we repeat the process till we reach the very bottom of the recursion, meaning we’ll only have slices consisting of 1 element, then start climbing back the recursion stairs by merging smaller slices into bigger ones, till there is nothing to merge anymore, resulting in a nicely sorted single slice.

# Merge Sort Algorithm Recipe

So, we’re getting closer to putting the *Merge Sort Algorithm* together, we just need to establish couple of things we’ll need and how we’re planning to do things around.

- We need a
that merges and sorts the final array/slice*Merge Function* - We need a
*recursive**Sort Function* - Call
for the*Sort recursively*&*LEFT*sides*RIGHT* - Call
for the sorted*Merge recursively*&*LEFT*sides*RIGHT* the*Return*back to the caller*sorted slice*

With all of the above steps, we can start having a look at the meat of the algorithm, meaning the ** merge **and the

**functions.**

*sort*# Merge Function

Right of the bat, the merge function’s responsibility is to ** merge 2** given arrays/slices

**, as well as**

*into 1***the result in the merging process.**

*sorting*So, the merge function that we have to create will primarily do these 3 things:

as many times as the*Iterate*arrays/slices, meaning if we pass a slice of*smallest length of the 2*and a slice of*length 7*, the loop will iterate*length 3*. This of course is for the*3 times only**highest efficiency*while doing comparisons.- On each iteration we
the elements of*compare*sides and*LEFT & RIGHT*the*insert*one in the*smaller**resulting array/slice*, till we run out of iterations. - We
all the*insert*, when we run out of iterations. Like the case when one side has the most smaller elements, the other side will have elements we have not inserted in the*missing elements**resulting array/slice*.

While the merge function does all the things we enumerated above, it does not do couple of things which We, the developers are responsible for before calling the merge function. There is 1 thing that the merge function expects the developer to take care of, in order for it to work correctly:

The

RIGHT & LEFTarrays/slicesMUST be Sorted

You may be thinking, if the arrays/slices have the *same length* then the check we make on each iteration should result in a correctly sorted slice. Well, that’s quite *not true*. We start running into *issues* when we have arrays/slices that either have *different lengths* or the elements on one side are *mostly sorted*. For example, running the following, will result in wrongly sorted results.

*merge*([]int{2,3,4,6}, []int{0,1,5,7,9,8}) // [0 1 2 3 4 5 3 6 9 8]

*merge*([]int{1,2,3,5}, []int{4,6,9,8}) // [1 2 3 4 5 6 9 8]

The merge function must be *able* to work with ** different** array/slice

**, however, because on every sort call we**

*lengths**divide*the array/slice in

*2*, it’s clear that the merge function will be called with

*n*or

*n+1*elements difference.

Here’s a small overview of the merge function and how it should work when for example we call it with the following *LEFT* & *RIGHT* sides:

*merge*([]int{*4,5,7*}, []int{*1,3,6*})

# Merge Function Pseudocode

functionmerge(L, R) {

letA[0..L.length+R.length]

i, j, k= 0, 0, 0// compare LEFT & RIGHT side elements before merging

while{i < L.length and j < R.length

if{L[i] < R[j]

A[k] = L[i]

i++

} else {

A[k] = R[j]

j++

}

}

// check if any elements from the left/right side

// were missed in the comparison section above

while{i < L.length

A[k] = L[i]

i++

k++

}

while{j < R.length

A[k] = R[j]

j++

k++

}

return A

}

As you can see from the pseudocode above we’re mainly doing 2 things:

- Compare the elements and decide which ones goes first in the resulting
array/slice.*A*

*...*

while *i < L.length and j < R.length* {

if *L[i] < R[j]* {

A[k] = L[i]

i++

} else {

A[k] = R[j]

j++

}

}

...

Also notice the ** sorting condition** above is hardcoded. Instead we could also receive a

**that accepts**

*callback function***and**

*a***and returns bool, giving the control of**

*b***to the**

*sorting**caller*.

*type *sortFunc *func*(a, b int) bool

2. At the end we check for any left elements and we add them at the end of the resulting array/slice *A*

...

while{i < L.length

A[k] = L[i]

i++

k++

}while{j < R.length

A[k] = R[j]

j++

k++

}return A

...

# Merge Function implemented in Go

The implementation translates more than 90% from the pseudocode above, so there’s really no need for any kind of explanations.

If you don’t want to run the code above on your machine, feel free to experiment with the *merge function repl**.*

To make the merge function ** less coupled** to the

**, we can go ahead and**

*sorting condition**accept*a

**that returns a**

*callback function**boolean*and leave this responsibility to the

**.**

*caller*If you don’t want to run the code above on your machine, feel free to experiment with the *merge function with sorting func repl**.*

# Sort Function

You may be asking yourself, how the hell do we sort things when all we do is ** merge 2 already sorted** arrays/slices and

**that uses merge**

*call a function***. Well that’s the beauty of the**

*recursively**Divide & Conquer*principle.

By ** dividing** the initial array/slice consisting of perhaps a huge amount of elements into

**and**

*smaller arrays/slices***the process we reach the very bottom of the recursion, where**

*repeating***an array/slice**

*by definition**consisting of 1 element*are trivially

**, which means when we**

*considered already sorted***we meet both conditions:**

*start merging*- We provide sorted LEFT & RIGHT side arrays/slices (beginning from arrays/slice of length 1)
- Repeat the process till we’ve merged everything back to the initial big array/slice, this time in the sorted order

Have a look at how exactly the ** sort** function will get called for a simple example like the following:

*sort*([]int{**6,2,1,3,5,4**}) // [1, 2, 3, 4, 5, 6]

# Sort Function Pseudocode

functionsort(A) {

ifA.length{> 1

n1= A.length/ 2

n2= A.length - n1

letL[0..n1] and R[0..n2]

// split A in half => L and R arrays/slices

fori=0 to n1 {

L[i] = A[i]

}

forj=0 to n2 {

R[j] = A[n1+j]

}

// for languages that use clever constructs

// m = A.length / 2

// L = A[:m]

// R = A[m:] // recursively sort & merge L & R arrays/slices

// A starts growing when recursion reaches the very bottom

A=(merge(L),sort(R))sort

}

// return when array/slice consists of 1 elementreturn A

}

The ** sort** function primarily consists of 3 steps:

the incoming array/slice*Split*, on every recursive call & create LEFT & RIGHT arrays/slices.*in 2 sides*

*...*

n1 = A.length */ 2*

*n2* = A.length - n1

*let* L[0..n1] and R[0..n2]

// split A in half => L and R arrays/slices

*for* i=0 to n1 {

*L[i] = A[i]*

}

*for* j=0 to n2 {

*R[j] = A[n1+j]*

}

...

2. ** Return** array/slice when it cannot be divided anymore, or it has

**.**

*only 1 element*if{A.length > 1

...

}// Here we have an array/slice of 1 element only

return A

3. Call ** sort** and

**for**

*merge***&**

*LEFT***sides recursively, till exit condition is met (array/slice has**

*RIGHT**1 element only*or

*both sides*were merged).

**...**

// recursively sort & merge L & R arrays/slices

// A starts growing when recursion reaches the very bottom

A = *merge*(*sort*(L), *sort*(R))

...

# Sort Function implemented in Go

The implementation translates more than 90% from the pseudocode above, so there’s really no need for any kind of explanations in this case as well.

If you don’t want to run the code above on your machine, feel free to experiment with the *sort function repl**.*

# CAN we IMPROVE it?

We all know there is no perfect way of doing things, like there is no perfect sorting algorithm. So here are couple of things we should know about the ** Merge Sort Algorithm**, which can suggest us ways we can improve its

**/**

*performance*

*memory**usage*

uses*Merge Sort*(L, R slices) this may be a problem for huge data sets where we deal with millions of objects that take up a lot of space.*temporary memory*works with giant data sets and is also stable &*Merge Sort*.*very predictable*

Now, while Merge Sort is considered a *decent* algorithm to deal with big data, it can be an issue for applications that heavily rely on memory.

However a while ago we studied the ** Insertion Sort Algorithm**, which we know that:

is*Insertion Sort*on small data sets*faster*does not use*Insertion Sort**temporary memory*

If you want to know more about the *Insertion Sort Algorithm*, make sure to check out the ** Medium article** or the

**, where I covered the algorithm in details. Choose whatever works better for you.**

*YouTube video*Now if you’re me, you may be asking yourself, why not ** combine the 2** so that we take the best out of both worlds and make our sorting as

**and**

*CPU***efficient as possible. Well, there is already an algorithm called**

*memory***aka**

*Insertion-Merge Sort,**Ford–Johnson algorithm,*which does exactly that.

So here’s how we’re going to use the 2 together:

- Use
most of the times*Merge Sort* the data*Check*before splitting the array/slice*length*- Use
instead if the data length is*Insertion Sort**small enough*

Now you may be asking yourself, what exactly ** small enough** means for

**? Well, that’s a good question. The generic answer is, use something between:**

*Insertion Sort***.**

*8–20 elements*However that is too generic, normally you want to ** test things out**, and

**it for the amount of data you are sorting. The bigger the threshold the more trouble the**

*adjust**Insertion Sort*will have if you will deal with big data like

*millions*or even

*billions*of elements. So you want to keep it low, but not too low, otherwise there is no use of the

*Insertion Sort*.

Here’s a different implementation of the sort function which implements all of the above:

If you don’t want to run the code on your machine, feel free to experiment with the *insertion merge sort repl*** . **And if you ran the example on your machine or inside the repl, you could see that we trivially and easily

**.**

*sorted 1 million records*As I said before the ** Merge Sort** or in this case the

**algorithm are both**

*Insertion Merge Sort***, meaning we can expect the same amount of execution time for most data.**

*very predictable*# Performance & Benchmarks

There’s no better proof than *numbers* & *benchmarks*. These show how would the algorithms approximately perform in the real world. These are the results I got on my personal *Macbook Pro 2019* machine, yours might be different:

`goos: darwin`

goarch: amd64

pkg: github.com/algorithms-go/sorting/sort

cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz

BenchmarkInsertionSort

BenchmarkInsertionSort-16 21 52535921 ns/op

PASS

goos: darwin

goarch: amd64

pkg: github.com/algorithms-go/sorting/sort

cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz

BenchmarkMergeSort

BenchmarkMergeSort-16 747 1608912 ns/op

PASS

goos: darwin

goarch: amd64

pkg: github.com/algorithms-go/sorting/sort

cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz

BenchmarkMergeSortFunc

BenchmarkMergeSortFunc-16 705 1614946 ns/op

PASS

goos: darwin

goarch: amd64

pkg: github.com/algorithms-go/sorting/sort

cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz

BenchmarkInsertionMergeSortFunc

BenchmarkInsertionMergeSortFunc-16 915 1293846 ns/op

Pay attention at the ** first number** which is

**the function was**

*how many times***in a small time window (**

*executed**bigger is better*) , and also at the

**which shows how many**

*second number***it took (**

*nanoseconds/operation**smaller is better*).

For benchmark tests have a look at the *benchmarks repl*** , **where there are regular

**, as well as the exact**

*tests***I ran on my machine. Or feel free to download the code directly from the**

*benchmarks***and run them on your machine. Enjoy.**

*repo*Again these results will vary from machine to machine, but generally they execute ** without issues** on most machines including

*single core*test servers like repl.it or Go Playgrounds. Feel free to run the tests and the benchmarks on your own and check the results for yourself:

You can also go ahead and run the exact same code inside the *benchmarks repl*** . **Even run the tests and benchmarks inside the

**.**

*console tab*# Merge Sort Facts

As I say in everyone of my tutorials, there is really ** no perfect tool/solution** or algorithm that does it all. You really have to

**for the**

*use the right tool***, or I should say use the right**

*right problem**Sorting Algorithm*for the right situation.

That’s why before we wrap this up, let’s explore couple of ** facts** about the

**, so that you know when is best to use it and when not:**

*Merge Sort Algorithm*- Merge Sort is
&*Efficient*for*Very Fast*sets*big data* - Merge Sort Time Complexity is:
*O(n*log(n))* - Merge Sort Space Complexity is:
*O(n)*

Here are couple of facts about the ** Insertion Sort Algorithm,** in case you did not check out the article or video above:

- Insertion Sort is
for*Efficient*sets*small data* - Insertion Sort
Time Complexity is:*Best**O(n)* - Insertion Sort
Time Complexity is:*Worst/Average**O(n*n)* - Insertion Sort Space Complexity is:
*O(1)*

Knowing the above facts, helps ** identify** &

**the sorting problem and give us an idea of how we shall proceed with sorting and what kind of sorting algorithms to use.**

*diagnose*# Conclusion

There is no ** all in 1 solution**, like there is no algorithm which

**the**

*works***in**

*best***. That’s why I wanna wrap up this article, by saying always**

*every case***. It’s never one versus the other, it’s one or the other, in fact most of the times problems require**

*choose the right algorithm for the right situation*

*hybrid***and a mix of a bunch of algorithms.**

*implementations*# Resources

Make sure to check out the GitHub ** repo** for all the

*presentation notes, animations*,

*coding examples*and more. Also make sure to check out this nice cheatsheet that very well explains the

**of most**

*Time Complexity**Sorting Algorithms*& not only.

# Let’s Connect

*Facebook**Twitter**Instagram**LinkedIn**Discord Community**YouTube*

# Support Me

I’ve recently gave up my job and I made YouTube and online content creation my ** full time job**. If you like what I do and find any value and want to be part of my dream feel free to support me on

*Patreon***or with a small**

**donation.**

*Paypal*