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).

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.