August 16, 2020

# Merge Sort In Go

Using divide and conquer to build merge sort in Go

Photo by Markus Spiske on Unsplash

## What is sorting?

Sorting is a way to organize data in certain order.

What are these orders?

It depends on the task and also on the type of data we are working with. For example, for number you can sort them in ascending or descending order of their values. And for text you can do the same based on the occurrence their character.

## What’s a “merge” sort?

It is a way to sort any data in which we divide the given task in subtasks
(in half) and ultimately *merging* those subtasks into one which gives us the
sorted list of the data which we want.

Here is a nice gif from WikiPedia for more graphical explanation.

It follows the divide and conquer design paradigm.

## 👨💻 Let’s write code

Suppose we have a list of array which holds integers. We will now write some Go code which will sort the integers using merge sort.

Since merge sort uses divide and conquer technique, it recursively do a function call to itself with the subtask and eventually merge the subtask into a single value of the sorted data.

This is how the merge step looks like.

### 🧪 Writing the test case first

```
package merge_sort
import (
"reflect"
"testing"
)
func TestMergeSort(t *testing.T) {
var tests = []struct {
message string
in []int
out []int
}{
{
"should return single value when input is single",
[]int{3},
[]int{3},
},
{
"should sort values in random order",
[]int{3, 1},
[]int{1, 3},
},
{
"should return empty array if the input is also empty",
[]int{},
[]int{},
},
{
"should sort values with duplication",
[]int{3, 2, 3},
[]int{2, 3, 3},
},
{
"should sort values with negative cases",
[]int{-9, 2, 3, -3},
[]int{-9, -3, 2, 3},
},
}
for _, tt := range tests {
t.Run(tt.message, func(t *testing.T) {
MergeSort(tt.in, 0, len(tt.in) - 1)
if reflect.DeepEqual(tt.in, tt.out) != true {
t.Errorf("got %q, want %q", tt.in, tt.out)
}
})
}
}
```

### Merge Step

```
// Merge left and right arrays
// start - start index of the array
// middle - middle index of the array
// end - end index of the array
func Merge(input []int, start, middle, end int) {
itemsAtLeftSide := middle - start + 1
itemsAtRightSide := end - middle
// creating arrays which holds one extra element then the
// currently needed because of the sentinel assignment
left := make([]int, itemsAtLeftSide + 1)
right := make([]int, itemsAtRightSide + 1)
// allocate elements in the left side of the array
for i := 0; i < itemsAtLeftSide; i++ {
left[i] = input[start + i]
}
// allocate elements in the right side of the array
for j := 0; j < itemsAtRightSide; j++ {
// adding one because because j index is staring from zero
// which in most of the cases conflict with the value in
// the left array, adding one removes the conflict element
right[j] = input[middle + j + 1]
}
// sentinel assignments
left[itemsAtLeftSide] = math.MaxInt64
right[itemsAtRightSide] = math.MaxInt64
for i, j, k := 0, 0, start; k <= end; k++ {
if left[i] <= right[j] {
// assign what is at the top of the left array
input[k] = left[i]
i++
} else {
// assign what is at the top of the right array
input[k] = right[j]
j++
}
}
}
```

### The Sorting Code

In merge sort the main part where we divide the task in half is simple. The real meat is the merging step which we have mentioned above.

```
func MergeSort(input []int, start, end int) {
if start < end {
// getting the middle value
middle := (start + end) / 2
// sort whatever in the left of the array
MergeSort(input, start, middle)
// sort whatever in the right of the array
MergeSort(input, middle + 1, end)
// merge left and right sorted values
Merge(input, start, middle, end)
}
}
```

### Playground Code 🏌️♂️

You can reach at the playground by following the link.