Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Merge Sort

Explore how merge sort works by recursively splitting arrays into halves and merging them in order. Learn to implement this stable sorting algorithm in Go, appreciating its O(n log n) performance across all cases and its ideal use with linked lists.

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

Go (1.6.2)
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)
...