Merge Sort
Let’s learn about the merge sort algorithm and its implementation.
We'll cover the following...
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 mainimport ("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) / 2mergeSrt(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 := lowerIndexlowerStop := middleIndexupperStart := middleIndex + 1upperStop := upperIndexcount := lowerIndexfor 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 Codefunc 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