I have written a merge sort algorithm program in go (see code below), but I am not getting the correct output.

The program below prints

[2 2 2 2 3]

but not the sorted array.

package main
import "fmt"
    
func MergeSort(arr []int) {
  if len(arr) < 2 {
    return
  }

  mid := len(arr) / 2
  left := arr[:mid]
  right := arr[mid:]
    
  MergeSort(left)
  MergeSort(right)
    
  merge(arr, left, right)
}

func merge(a []int, l []int, r []int) {
  i := 0
  j := 0
  k := 0

  for i < len(l) && j < len(r) {
    if l[i] <= r[j] {
      a[k] = l[i]
      i  
    } else {
      a[k] = r[j]
      j  
    }
    k  
  }
  
  for i < len(l) {
    a[k] = l[i]
    i  
    k  
  }
  
  for j < len(r) {
    a[k] = r[j]
    j  
    k  
  }

}

func main() {
  t := []int{23, 67, 98, 2, 3}
  MergeSort(t)
  fmt.Println(t)
}

CodePudding user response：

Be aware that my solution just fixes the bug in the code, and does not solve performance problems. I also advise testing it on a random set of integers and checking if the slice is sorted.

package main

import "fmt"

func main() {
    t := []int{23, 67, 98, 2, 3}
    MergeSort(t)
    fmt.Println(t)
}

func MergeSort(arr []int) {
    if len(arr) < 2 {
        return
    }
    mid := len(arr) / 2
   
    // these lines are important, you cannot do split sort 
    // in-place like you did because the memory would get 
    // corrupted as you join slice into itself.
    left := append([]int{}, arr[:mid]...)

    right := append([]int{}, arr[mid:]...)

    MergeSort(left)
    MergeSort(right)

    merge(arr, left, right)
}

func merge(a []int, l []int, r []int) {
    i := 0
    j := 0
    k := 0
    for i < len(l) && j < len(r) {
        if l[i] <= r[j] {
            a[k] = l[i]
            i  
        } else {
            a[k] = r[j]
            j  
        }
        k  
    }
    for i < len(l) {
        a[k] = l[i]
        i  
        k  
    }

    for j < len(r) {
        a[k] = r[j]
        j  
        k  
    }
}

CodePudding user response：

A slice is just a window onto an array that is the backing store for the slice.

The problem is almost certainly this:

mid := len(arr) / 2
left := arr[:mid]
right := arr[mid:]

That creates 2 new slices, but they are just windows onto the same array, so when you divide the source slice into left/right halves, the two new slices share the same backing store — the array that backs the original slice. It does not copy the backing store.

Further, when you merge, you're trying to merge back into the same, original array.

So you are trying to do everything in place within the same base array. And that doesn't work, in particular, in-place merging.

You need to clone your slices as you split and merge, using make() and copy(). That leads you to this implementation, which you can fiddle with here in the Go Playground.

Where merge sort shines is sorting linked lists, as no extra space is required. That's already present in the form of each node's pointer to the next node:

package main

import (
  "fmt"
)

func main() {
  unsorted := []int{10, 1, 9, 2, 8, 3, 7, 4, 6, 5, 0, 5, 6, 4, 7, 3, 8, 2, 9, 1, 10}
  sorted := sort(unsorted)

  fmt.Println(sorted)
}

func sort(unsorted []int) []int {

  // get the length of the source slice
  n := len(unsorted)

  // The terminating special case:
  // slices of length <= 1 is sorted by definition
  if n <= 1 {
    return clone(unsorted)
  }

  // compute the offset to the midpoint
  m := n / 2

  // divide the source slice into two halves,
  // then recursively sort them,
  // and merge them to produce the sorted slice
  sorted := merge(
    sort(clone(unsorted[:m])),
    sort(clone(unsorted[m:])),
  )
  return sorted
}

func merge(a []int, b []int) []int {
  aMax := len(a)
  bMax := len(b)

  // construct a new slice to contain the merger of the two slices
  c := make([]int, aMax bMax)

  // initialize our indices
  i := 0 // offset to the current element in the 'a' slice
  j := 0 // offset to the current element in the 'b' slice
  k := 0 // offset to the current element in the 'c' slice

  // while we have both an 'a' element and a 'b' element...
  for i < aMax && j < bMax {

    if a[i] <= b[j] {
      c[k] = a[i]
      i  
    } else {
      c[k] = b[j]
      j  
    }

    k  
  }

  // if we have any 'a' elements remaining, take them
  for ; i < aMax; k   {
    c[k] = a[i]
    i  
  }

  // if we have any 'b' elements remaining, take them.
  for ; j < bMax; k   {
    c[k] = b[j]
    j  
  }

  // return the merger of the two slices
  return c
}

func clone(arr []int) []int {
  arr1 := make([]int, len(arr))
  copy(arr1, arr)
  return arr1
}