Merge Sort

Let’s learn about the merge sort algorithm and its implementation.

Introduction

Merge sort recursively partitions the input into two halves. The two halves are then sorted independently before being combined into the final sorted output. The recursive step keeps on dividing the input into smaller pieces until the length of each piece becomes one.

Let’s look at an illustration of the merge sort in action.

Code example

Press + to interact
package main
import ("fmt")
func MergeSort(arr []int) {
size := len(arr)
tempArray := make([]int, size)
mergeSrt(arr, tempArray, 0, size-1)
}
func mergeSrt(arr []int, tempArray []int, lowerIndex int, upperIndex int) {
if lowerIndex >= upperIndex {
return
}
middleIndex := (lowerIndex + upperIndex) / 2
mergeSrt(arr, tempArray, lowerIndex, middleIndex)
mergeSrt(arr, tempArray, middleIndex+1, upperIndex)
merge(arr, tempArray, lowerIndex, middleIndex, upperIndex)
}
func merge(arr []int, tempArray []int, lowerIndex int, middleIndex int, upperIndex int) {
lowerStart := lowerIndex
lowerStop := middleIndex
upperStart := middleIndex + 1
upperStop := upperIndex
count := lowerIndex
for lowerStart <= lowerStop && upperStart <= upperStop {
if arr[lowerStart] < arr[upperStart] {
tempArray[count] = arr[lowerStart]
lowerStart++
} else {
tempArray[count] = arr[upperStart]
upperStart++
}
count++
}
for lowerStart <= lowerStop {
tempArray[count] = arr[lowerStart]
count++
lowerStart++
}
for upperStart <= upperStop {
tempArray[count] = arr[upperStart]
count++
upperStart++
}
for i := lowerIndex; i <= upperIndex; i++ {
arr[i] = tempArray[i]
}
}
//Testing Code
func main() {
data := []int{9, 1, 8, 2, 7, 3, 6, 4, 5}
MergeSort(data)
fmt.Println(data)
}

Analysis

  • The time complexity of merge sort is O(nlogn)O(nlogn)
...