# Sorting with different Algorithms

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

• Can you provide full code of example for running? Or add link to playground.
– user110702
Dec 23, 2017 at 6:22
• Just added a link to a gist; was getting an internal server error when trying to share a go playground. Dec 23, 2017 at 14:58

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++
}
}