Merge sort is a very good example of the divide-and-conquer paradigm. Here is a flaky implementation of merge sort for sorting arrays of integers in Go. You have a merge function:
// merge function.
func merge(a, b []int) []int {
la, lb := len(a), len(b)
i, j := 0, 0
n := la + lb
c := make([]int, n)
for k := 0; k < n; k++ {
if (i < la) && (j < lb) {
if a[i] < b[j] {
c[k] = a[i]
i++
} else {
c[k] = b[j]
j++
}
} else if i > la-1 {
c[k] = b[j]
j++
} else {
c[k] = a[i]
i++
}
}
return c
}
And a sort function that is recursive:
// sort function.
func sort(x []int) []int {
n := len(x)
if (n == 0) || (n == 1) {
return x
}
h := n / 2
a := sort(x[:h])
b := sort(x[h:])
return merge(a, b)
}
Further work include figuring out a nice abstraction in order to apply this to sorting other kinds of arrays.