Sorting with different Algorithms

Question

I'm new to Go, so I implemented a few sorting algorithms for practice. For example, I have an in-place insertion sort, and a bubble sort:

func bubbleSort(arr []int) {
 for i := 1; i < len(arr); i++ {
 if arr[i] < arr[i - 1] {
 tmp := arr[i - 1]
 arr[i - 1] = arr[i]
 arr[i] = tmp
 i = 0
 }
 }
}
func insertionSort(arr []int) {
 for i := 0; i < len(arr); i++ {
 for j := 0; j < i; j++ {
 if arr[j] > arr[i] {
 tmp := arr[j]
 arr[j] = arr[i]
 arr[i] = tmp
 }
 }
 }
}

However, when I went to implement merge sort, I found it most natural to use return values, because I couldn't seem to find a clean way to merge the results in place. Is there a good way to do this in Go, and would it even make sense to do so in-place? Or would it lead to difficulties when attempting to move to a concurrent implementation using goroutines? Code:

func merge(pt1 []int, pt2 []int) []int {
 totalLen := len(pt1) + len(pt2)
 arr := []int{}
 for i := 0; i < totalLen; i++ {
 // remove the smallest from the 2 slices and add it to the final
 if pt1[0] < pt2[0] {
 arr = append(arr, pt1[0])
 pt1 = pt1[1:]
 } else {
 arr = append(arr, pt2[0])
 pt2 = pt2[1:]
 }
 // break if a slice has been emptied
 if len(pt1) == 0 || len(pt2) == 0 {
 break
 }
 }
 arr = append(arr, pt1...)
 return append(arr, pt2...)
}
// merge sort algorithm
func mergeSort(arr []int) []int {
 arrLen := len(arr)
 if arrLen > 1 {
 pt1 := mergeSort(arr[arrLen/2:])
 pt2 := mergeSort(arr[:arrLen/2])
 arr = merge(pt1, pt2)
 }
 return arr
}

Any general style tips are also greatly appreciated (link to full code).

• user110702: Can you provide full code of example for running? Or add link to playground.
• treyhakanson: Just added a link to a gist; was getting an internal server error when trying to share a go playground.

Answer 1

I'm not pretend to full review, but I guess better so than nothing.

1. Golang allow swapping in one-line, so you can just do so:

   arr[i-1],arr[i] = arr[i],arr[i-1]

2. Go does not have optional parameters nor does it support method overloading.So if you want implement more "usually" version of this sort - provide utility function which will take arguments for range:

   // merge sort algorithm
   func merge_sort(arr []int, l, r int) {
    if l < r {
    m := (l + r) / 2
    mergeSort(arr, l, m)
    mergeSort(arr, m+1, r)
    merge(arr, l, m, r)
    }
   }
   func mergeSort(arr []int) {
    merge_sort(arr, 0, len(arr)-1)
   }
   

3. In your current code very often used function append, it's not very effective. As example I just re-write C code from here and get:

   func merge(arr []int, l, m, r int) {
    i := 0
    j := 0
    k := 0
    n1 := m - l + 1
    n2 := r - m
    L := make([]int, n1)
    R := make([]int, n2)
    for i < n1 {
    L[i] = arr[l+i]
    i++
    }
    for j < n2 {
    R[j] = arr[m+1+j]
    j++
    }
    i = 0
    j = 0
    k = l
    for i < n1 && j < n2 {
    if L[i] <= R[j] {
    arr[k] = L[i]
    i++
    } else {
    arr[k] = R[j]
    j++
    }
    k++
    }
    for i < n1 {
    arr[k] = L[i]
    i++
    k++
    }
    for j < n2 {
    arr[k] = R[j]
    j++
    k++
    }
   }
   

4. About concurrent implementation - read this question and answers and this one.