👋 Welcome Gophers! In this lesson, we are going to implement the merge sort algorithm that we looked at in the previous lesson.
Implementation
Let’s start by creating a new file called main.go in a directory called 03-merge-sort/. We’ll build up the merge sort implementation step by step.
Let’s start with the basic setup:
package main
import "fmt"
func main() {
fmt.Println("Merge Sort Algorithm in Go")
}
Now, let’s define the function signatures for our merge sort functions. We need two functions: one for the main merge sort logic and one for merging two sorted slices:
// MergeSort - takes in a slice of ints and returns a sorted slice of ints
func MergeSort(input []int) []int {
}
// Merge - takes two sorted slices and merges them into a single sorted slice
func Merge(left, right []int) []int {
}
Let’s start with the Merge function first since it’s simpler. This function takes two already-sorted slices and combines them into a single sorted slice:
func Merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
// iterate through both slices and add the smaller element to result
for len(left) > 0 || len(right) > 0 {
// if left is empty, add all remaining elements from right
if len(left) == 0 {
return append(result, right...)
}
// if right is empty, add all remaining elements from left
if len(right) == 0 {
return append(result, left...)
}
// compare first elements and add the smaller one
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
return result
}
The Merge function works by comparing the first elements of each slice and adding the smaller one to the result. We continue until both slices are empty.
Now let’s implement the MergeSort function, which uses the divide-and-conquer approach:
func MergeSort(input []int) []int {
// base case: arrays with 0 or 1 element are already sorted
if len(input) <= 1 {
return input
}
// divide the array into two halves
middle := len(input) / 2
left := MergeSort(input[:middle])
right := MergeSort(input[middle:])
// merge the sorted halves
return Merge(left, right)
}
This is elegant! The function:
- Checks if the input has 1 or fewer elements (base case)
- Divides the input in half
- Recursively sorts each half
- Merges the sorted halves back together
Now let’s test it out by creating a slice in our main function and calling our new MergeSort function:
func main() {
fmt.Println("Merge Sort Algorithm in Go")
unsortedInput := []int{5, 3, 4, 1, 2}
fmt.Println("Before:", unsortedInput)
sorted := MergeSort(unsortedInput)
fmt.Println("After:", sorted)
}
Perfect! Let’s run this from the command line:
$ go run main.go
Merge Sort Algorithm in Go
Before: [5 3 4 1 2]
After: [1 2 3 4 5]
Excellent! Our merge sort is working correctly. Let’s add a version with some debug output to see what’s happening at each step:
func MergeSortDebug(input []int, depth int) []int {
indent := ""
for i := 0; i < depth; i++ {
indent += " "
}
fmt.Printf("%sDividing: %v\n", indent, input)
if len(input) <= 1 {
return input
}
middle := len(input) / 2
left := MergeSortDebug(input[:middle], depth+1)
right := MergeSortDebug(input[middle:], depth+1)
result := Merge(left, right)
fmt.Printf("%sMerged: %v\n", indent, result)
return result
}
Now when we call it with debug output, we can see exactly how the array is being divided and merged:
$ go run main.go
Merge Sort Algorithm in Go
Before: [5 3 4 1 2]
Dividing: [5 3 4 1 2]
Dividing: [5 3 4]
Dividing: [5 3]
Dividing: [5]
Dividing: [3]
Merged: [3 5]
Dividing: [4]
Merged: [3 4 5]
Dividing: [1 2]
Dividing: [1]
Dividing: [2]
Merged: [1 2]
Merged: [1 2 3 4 5]
After: [1 2 3 4 5]
Perfect! You can see how the algorithm divides the array all the way down to single elements, then merges them back together in sorted order.
Testing
Let’s create a proper test to validate our implementation:
func TestMergeSort(t *testing.T) {
tests := []struct {
input []int
expected []int
}{
{[]int{5, 3, 4, 1, 2}, []int{1, 2, 3, 4, 5}},
{[]int{1}, []int{1}},
{[]int{}, []int{}},
{[]int{2, 1}, []int{1, 2}},
{[]int{1, 2, 3, 4, 5}, []int{1, 2, 3, 4, 5}},
{[]int{5, 4, 3, 2, 1}, []int{1, 2, 3, 4, 5}},
}
for _, tt := range tests {
sorted := MergeSort(tt.input)
if !slicesEqual(sorted, tt.expected) {
t.Errorf("MergeSort(%v) = %v, want %v", tt.input, sorted, tt.expected)
}
}
}
func slicesEqual(a, b []int) bool {
if len(a) != len(b) {
return false
}
for i := range a {
if a[i] != b[i] {
return false
}
}
return true
}
Conclusion
Awesome! We now have a working implementation of the merge sort algorithm in Go! This algorithm is much more efficient than bubble sort or insertion sort for larger datasets because it guarantees O(n log n) performance. The divide-and-conquer approach makes it easy to understand and implement correctly.
Quiz Time
Try your hand at these questions below to validate what we’ve just covered in this lesson: